/LMAR=0/XLINE=3/FONT#0=BAXL30/FONT#1=BAXM30/FONT#2=BASB30/FONT#3=SUB/FONT#4=SUP/FONT#5=BASL35/FONT#6=NGR25/FONT#7=MATH30/FONT#8=FIX25/FONT#9=GRKB30
␈↓ α∧␈↓␈↓ u1


␈↓ α∧␈↓α␈↓ ¬{HISTORY OF LISP

␈↓ α∧␈↓␈↓ ε≥John McCarthy
␈↓ α∧␈↓␈↓ ¬.Artificial Intelligence Laboratory
␈↓ α∧␈↓␈↓ εβStanford University




␈↓ α∧␈↓␈↓↓This␈α∪draft␈α∪gives␈α∪insufficient␈α∪mention␈α∪to␈α∪many␈α∪people␈α∪who␈α∪helped␈α∪implement␈α∪LISP␈α∀and␈α∪who
␈↓ α∧␈↓↓contributed␈αideas.␈α Suggestions␈αfor␈αimprovements␈α
in␈αthat␈αdirections␈αare␈αparticularly␈αwelcome.␈α
 Facts
␈↓ α∧␈↓↓about the history of FUNARG and uplevel addressing generally are especially needed␈↓.

␈↓ α∧␈↓1. Introduction.

␈↓ α∧␈↓␈↓ αTThis␈α∩paper␈α∪concentrates␈α∩on␈α∩the␈α∪development␈α∩of␈α∩the␈α∪basic␈α∩ideas␈α∩and␈α∪distinguishes␈α∩two
␈↓ α∧␈↓periods␈α-␈αSummer␈α1956␈αthrough␈αSummer␈α1958␈αwhen␈αmost␈αof␈αthe␈αkey␈αideas␈αwere␈αdeveloped␈α(some
␈↓ α∧␈↓of␈αwhich␈αwere␈αimplemented␈α
in␈αthe␈αFORTRAN␈αbased␈αFLPL),␈α
and␈αFall␈α1958␈αthrough␈α
1962␈αwhen
␈↓ α∧␈↓the␈α∂programming␈α⊂language␈α∂was␈α∂implemented␈α⊂and␈α∂applied␈α∂to␈α⊂problems␈α∂of␈α⊂artificial␈α∂intelligence.
␈↓ α∧␈↓After␈α1962,␈αthe␈αdevelopment␈αof␈αLISP␈α
became␈αmulti-stranded,␈αand␈αdifferent␈αideas␈αwere␈αpursued␈α
in
␈↓ α∧␈↓different places.

␈↓ α∧␈↓␈↓ αTExcept␈αwhere␈αI␈αgive␈αcredit␈αto␈αsomeone␈αelse␈αfor␈αan␈αidea␈αor␈αdecision,␈αI␈αshould␈αbe␈αregarded␈αas
␈↓ α∧␈↓tentatively␈α⊃claiming␈α⊃credit␈α⊃for␈α⊃it␈α⊃or␈α∩else␈α⊃regarding␈α⊃it␈α⊃as␈α⊃a␈α⊃consequence␈α⊃of␈α∩previous␈α⊃decisions.
␈↓ α∧␈↓However,␈α∞I␈α
have␈α∞made␈α∞mistakes␈α
about␈α∞such␈α∞matters␈α
in␈α∞the␈α
past,␈α∞and␈α∞I␈α
have␈α∞received␈α∞very␈α
little
␈↓ α∧␈↓response␈α⊃to␈α⊃requests␈α⊂for␈α⊃comments␈α⊃on␈α⊂drafts␈α⊃of␈α⊃this␈α⊂paper.␈α⊃ It␈α⊃is␈α⊂particularly␈α⊃easy␈α⊃to␈α⊃take␈α⊂as
␈↓ α∧␈↓obvious␈α∞a␈α∞feature␈α∞that␈α∞cost␈α
someone␈α∞else␈α∞considerable␈α∞thought␈α∞long␈α
ago.␈α∞ As␈α∞the␈α∞writing␈α∞of␈α
this
␈↓ α∧␈↓paper␈α
approaches␈α
its␈α∞conclusion,␈α
I␈α
have␈α∞become␈α
aware␈α
of␈α∞additional␈α
sources␈α
of␈α∞information␈α
and
␈↓ α∧␈↓additional areas of uncertainty.

␈↓ α∧␈↓␈↓ αTAs␈αa␈αprogramming␈αlanguage,␈αLISP␈αis␈αcharacterized␈αby␈αthe␈αfollowing␈αideas:␈αcomputing␈αwith
␈↓ α∧␈↓symbolic␈α∪expressions␈α∪rather␈α∪than␈α∪numbers,␈α∪representation␈α∪of␈α∪symbolic␈α∪expressions␈α∪and␈α∩other
␈↓ α∧␈↓information␈α⊃by␈α∩list␈α⊃structure␈α⊃in␈α∩the␈α⊃memory␈α∩of␈α⊃a␈α⊃computer,␈α∩representation␈α⊃of␈α∩information␈α⊃in
␈↓ α∧␈↓external␈αmedia␈α
mostly␈αby␈αmulti-level␈α
lists␈αand␈αsometimes␈α
by␈αS-expressions,␈αa␈α
small␈αset␈α
of␈αselector
␈↓ α∧␈↓and␈αconstructor␈αoperations␈αexpressed␈αas␈αfunctions,␈αcomposition␈αof␈αfunctions␈αas␈αa␈αtool␈α
for␈αforming
␈↓ α∧␈↓more␈α∂complex␈α∂functions,␈α∞the␈α∂use␈α∂of␈α∞conditional␈α∂expressions␈α∂for␈α∞getting␈α∂branching␈α∂into␈α∞function
␈↓ α∧␈↓definitions,␈α↔the␈α⊗recursive␈α↔use␈α⊗of␈α↔conditional␈α↔expressions␈α⊗as␈α↔a␈α⊗sufficient␈α↔tool␈α↔for␈α⊗building
␈↓ α∧␈↓computable␈α
functions,␈αthe␈α
use␈αof␈α
λ-expressions␈α
for␈αnaming␈α
functions,␈αthe␈α
representation␈α
of␈αLISP
␈↓ α∧␈↓programs␈α⊃as␈α⊃LISP␈α⊃data,␈α⊃the␈α⊃conditional␈α⊃expression␈α⊃interpretation␈α⊃of␈α⊃Boolean␈α⊃connectives,␈α⊃the
␈↓ α∧␈↓LISP␈αfunction␈α␈↓↓eval␈↓␈αthat␈αserves␈αboth␈αas␈αa␈αformal␈αdefinition␈αof␈αthe␈αlanguage␈αand␈αas␈αan␈αinterpreter,
␈↓ α∧␈↓and␈α∂garbage␈α∞collection␈α∂as␈α∂a␈α∞means␈α∂of␈α∂handling␈α∞the␈α∂erasure␈α∂problem.␈α∞ LISP␈α∂statements␈α∂are␈α∞also
␈↓ α∧␈↓used as a command language when LISP is used in a time-sharing environment.

␈↓ α∧␈↓␈↓ αTSome␈α
of␈αthese␈α
ideas␈αwere␈α
taken␈αfrom␈α
other␈αlanguages,␈α
but␈αmost␈α
were␈αnew.␈α
 Towards␈αthe␈α
end
␈↓ α∧␈↓of␈αthe␈αinitial␈αperiod,␈αit␈αbecame␈αclear␈αthat␈αthis␈αcombination␈αof␈αideas␈αmade␈αan␈αelegant␈αmathematical
␈↓ α∧␈↓system␈αas␈αwell␈αas␈αa␈αpractical␈αprogramming␈αlanguage.␈α Then␈αmathematical␈αneatness␈αbecame␈αa␈αgoal
␈↓ α∧␈↓and␈α
led␈α
to␈α
pruning␈α
some␈α
features␈α
from␈α
the␈α
core␈α
of␈α
the␈α
language.␈α
 This␈α
was␈α
partly␈α
motivated␈α
by
␈↓ α∧␈↓esthetic␈αreasons␈αand␈α
partly␈αby␈αthe␈αbelief␈α
that␈αit␈αwould␈αbe␈α
easier␈αto␈αdevise␈αtechniques␈α
for␈αproving
␈↓ α∧␈↓programs␈α↔correct␈α↔if␈α↔the␈α⊗semantics␈α↔were␈α↔compact␈α↔and␈α⊗without␈α↔exceptions.␈α↔ The␈α↔results␈α⊗of
␈↓ α∧␈↓␈↓ u2


␈↓ α∧␈↓(Cartwright␈α1976)␈αand␈α(Cartwright␈αand␈αMcCarthy␈α1978),␈αwhich␈αshow␈αthat␈αLISP␈αprograms␈αcan␈αbe
␈↓ α∧␈↓interpreted␈α∩as␈α∩sentences␈α∩and␈α∪schemata␈α∩of␈α∩first␈α∩order␈α∪logic,␈α∩provide␈α∩new␈α∩confirmation␈α∪of␈α∩the
␈↓ α∧␈↓original intuition that logical neatness would pay off.

␈↓ α∧␈↓2. LISP prehistory - Summer 1956 through Summer 1958.

␈↓ α∧␈↓␈↓ αTMy␈α∞desire␈α∞for␈α∂an␈α∞algebraic␈α∞list␈α∂processing␈α∞language␈α∞for␈α∂artificial␈α∞intelligence␈α∞work␈α∂on␈α∞the
␈↓ α∧␈↓IBM␈α704␈αcomputer␈αarose␈α
in␈αthe␈αsummer␈αof␈α1956␈α
during␈αthe␈αDartmouth␈αSummer␈αResearch␈α
Project
␈↓ α∧␈↓on␈αArtificial␈αIntelligence␈αwhich␈αwas␈αthe␈αfirst␈αorganized␈αstudy␈αof␈αAI.␈α During␈αthis␈αmeeting,␈αNewell,
␈↓ α∧␈↓Shaw␈α
and␈α
Simon␈α
described␈α
IPL␈α
2,␈α
a␈α
list␈α
processing␈α
language␈α
for␈α
Rand␈αCorporation's␈α
JOHNNIAC
␈↓ α∧␈↓computer␈α
in␈α
which␈αthey␈α
implemented␈α
their␈αLogic␈α
Theorist␈α
program.␈α There␈α
was␈α
little␈αtemptation
␈↓ α∧␈↓to␈αcopy␈αIPL,␈αbecause␈αits␈αform␈αwas␈αbased␈αon␈αa␈αJOHNNIAC␈αloader␈αthat␈αhappened␈αto␈αbe␈αavailable
␈↓ α∧␈↓to␈α∞them,␈α∞and␈α∞because␈α∞the␈α∞FORTRAN␈α∞idea␈α∞of␈α∞writing␈α∞programs␈α∞algebraically␈α∞was␈α∂attractive.␈α∞ It
␈↓ α∧␈↓was␈α
immediately␈α
apparent␈αthat␈α
arbitrary␈α
subexpressions␈α
of␈αsymbolic␈α
expressions␈α
could␈αbe␈α
obtained
␈↓ α∧␈↓by␈α
composing␈α
the␈αfunctions␈α
that␈α
extract␈α
immediate␈αsubexpressions,␈α
and␈α
this␈α
seemed␈αreason␈α
enough
␈↓ α∧␈↓to go to an algebraic language.

␈↓ α∧␈↓␈↓ αTThere␈α
were␈α
two␈α
motivations␈α
for␈α
developing␈α
a␈α
language␈α
for␈α
the␈α
IBM␈α
704.␈α
 First,␈α∞IBM␈α
was
␈↓ α∧␈↓generously␈α∞establishing␈α∞a␈α∞New␈α∞England␈α∞Computation␈α∞Center␈α∞at␈α∞M.I.T.␈α∞which␈α∞Dartmouth␈α
would
␈↓ α∧␈↓use.␈α
 Second,␈αIBM␈α
was␈α
undertaking␈αto␈α
develop␈α
a␈αprogram␈α
for␈α
proving␈αtheorems␈α
in␈αplane␈α
geometry
␈↓ α∧␈↓(based␈αon␈αan␈αidea␈αof␈αMarvin␈α
Minsky's),␈αand␈αI␈αwas␈αto␈αserve␈α
as␈αa␈αconsultant␈αto␈αthat␈αproject.␈α At␈α
the
␈↓ α∧␈↓time,␈αIBM␈αlooked␈αlike␈αa␈αgood␈αbet␈αto␈αpursue␈αartificial␈αintelligence␈αresearch␈αvigorously,␈αand␈αfurther
␈↓ α∧␈↓projects␈αwere␈αexpected.␈α It␈αwas␈αnot␈αthen␈αclear␈αwhether␈αIBM's␈αFORTRAN␈αproject␈αwould␈αlead␈αto␈αa
␈↓ α∧␈↓language␈α∪within␈α∪which␈α∪list␈α∪processing␈α∪could␈α∪conveniently␈α∪be␈α∪carried␈α∪out␈α∪or␈α∪whether␈α∪a␈α∪new
␈↓ α∧␈↓language␈αwould␈αbe␈αrequired.␈α However,␈αmany␈αconsiderations␈αwere␈αindependent␈αof␈αhow␈αthat␈αmight
␈↓ α∧␈↓turn out.

␈↓ α∧␈↓␈↓ αTApart␈α
from␈α
consulting␈α
on␈αthe␈α
geometry␈α
program,␈α
my␈αown␈α
research␈α
in␈α
artificial␈αintelligence
␈↓ α∧␈↓was␈α
proceeding␈α
along␈αthe␈α
lines␈α
that␈αled␈α
to␈α
the␈αAdvice␈α
Taker␈α
proposal␈αin␈α
1958␈α
(McCarthy␈α1959).
␈↓ α∧␈↓This␈α∀involved␈α∀representing␈α∀information␈α∪about␈α∀the␈α∀world␈α∀by␈α∪sentences␈α∀in␈α∀a␈α∀suitable␈α∪formal
␈↓ α∧␈↓language␈α∞and␈α∞a␈α∞reasoning␈α∞program␈α∞that␈α∞would␈α∞decide␈α∞what␈α∞to␈α∞do␈α∞by␈α∞making␈α∞logical␈α
inferences.
␈↓ α∧␈↓Representing␈α∂sentences␈α⊂by␈α∂list␈α∂structure␈α⊂seemed␈α∂appropriate␈α∂-␈α⊂it␈α∂still␈α∂is␈α⊂-␈α∂and␈α∂a␈α⊂list␈α∂processing
␈↓ α∧␈↓language␈α
also␈α∞seemed␈α
appropriate␈α
for␈α∞programming␈α
the␈α
operations␈α∞involved␈α
in␈α
deduction␈α∞-␈α
and
␈↓ α∧␈↓still is.

␈↓ α∧␈↓␈↓ αTThis␈α
internal␈α
representation␈α
of␈α
symbolic␈α
information␈α
gives␈α
up␈α
the␈α
familiar␈α
infix␈α
notations␈α
in
␈↓ α∧␈↓favor␈α∂of␈α∂a␈α∂notation␈α∂that␈α∂simplifies␈α⊂the␈α∂task␈α∂of␈α∂programming␈α∂the␈α∂substantive␈α⊂computations,␈α∂e.g.
␈↓ α∧␈↓logical␈αdeduction␈αor␈αalgebraic␈αsimplification,␈αdifferentiation␈αor␈αintegration.␈α If␈αcustomary␈αnotations
␈↓ α∧␈↓are␈αto␈αbe␈αused␈αexternally,␈αtranslation␈αprograms␈αmust␈αbe␈αwritten.␈α Thus␈αmost␈αLISP␈αprograms␈αuse␈αa
␈↓ α∧␈↓prefix␈α
notation␈α
for␈α
algebraic␈α
expressions,␈α
because␈α
they␈α
usually␈α
must␈α
determine␈α
the␈α
main␈α
connective
␈↓ α∧␈↓before␈α∀deciding␈α∀what␈α∀to␈α∀do␈α∀next.␈α∃ In␈α∀this␈α∀LISP␈α∀differs␈α∀from␈α∀almost␈α∀every␈α∃other␈α∀symbolic
␈↓ α∧␈↓computation␈α→system.␈α_ COMIT,␈α→FORMAC,␈α_and␈α→Formula␈α_Algol␈α→programs␈α_all␈α→express␈α_the
␈↓ α∧␈↓computations␈α∞as␈α∞operations␈α∞on␈α∞some␈α∞approximation␈α∞to␈α∞the␈α∞customary␈α∞printed␈α∞forms␈α∂of␈α∞symbolic
␈↓ α∧␈↓expressions.␈α SNOBOL␈α
operates␈αon␈α
character␈αstrings␈α
but␈αis␈α
neutral␈αon␈α
how␈αcharacter␈α
strings␈αare
␈↓ α∧␈↓used␈α⊂to␈α⊂represent␈α⊂symbolic␈α⊂information.␈α⊂ This␈α⊂feature␈α⊂probably␈α⊂accounts␈α⊂for␈α⊂LISP's␈α⊂success␈α⊂in
␈↓ α∧␈↓competition␈α∪with␈α∪these␈α∪languages,␈α∪especially␈α∪when␈α∪large␈α∪programs␈α∪have␈α∪to␈α∪be␈α∪written.␈α∪ The
␈↓ α∧␈↓advantage is like that of binary computers over decimal - but larger.

␈↓ α∧␈↓(In␈α∪the␈α∩late␈α∪1950s,␈α∩neat␈α∪output␈α∩and␈α∪convenient␈α∩input␈α∪notation␈α∩was␈α∪not␈α∪generally␈α∩considered
␈↓ α∧␈↓␈↓ u3


␈↓ α∧␈↓important.␈α
 Programs␈αto␈α
do␈α
the␈αkind␈α
of␈αinput␈α
and␈α
output␈αcustomary␈α
today␈α
wouldn't␈αeven␈α
fit␈αin␈α
the
␈↓ α∧␈↓memories␈αavailable␈αat␈αthat␈αtime.␈α Moreover,␈αkeypunches␈αand␈αprinters␈αwith␈αadequate␈αcharacter␈αsets
␈↓ α∧␈↓didn't exist).

␈↓ α∧␈↓␈↓ αTThe␈αfirst␈α
problem␈αwas␈α
how␈αto␈α
do␈αlist␈α
structure␈αin␈α
the␈αIBM␈α
704.␈α This␈α
computer␈αhas␈α
a␈α36␈α
bit
␈↓ α∧␈↓word,␈α⊃and␈α⊃two␈α⊃15␈α⊃bit␈α⊃parts,␈α⊃called␈α⊃the␈α⊃address␈α⊃and␈α⊃decrement,␈α⊃were␈α⊃distinguished␈α∩by␈α⊃special
␈↓ α∧␈↓instructions␈αfor␈αmoving␈αtheir␈αcontents␈αto␈αand␈αfrom␈αthe␈α15␈αbit␈αindex␈αregisters.␈α The␈αaddress␈αof␈αthe
␈↓ α∧␈↓machine␈α
was␈α
15␈α
bits,␈α
so␈α
it␈α
was␈α
clear␈α
that␈α
list␈α
structure␈α
should␈α
use␈α
15␈α
bit␈α
pointers.␈α
 Therefore,␈α
it␈α
was
␈↓ α∧␈↓natural␈α∞to␈α∞consider␈α∂the␈α∞word␈α∞as␈α∞divided␈α∂into␈α∞4␈α∞parts,␈α∞the␈α∂address␈α∞part,␈α∞the␈α∞decrement␈α∂part,␈α∞the
␈↓ α∧␈↓prefix␈αpart␈αand␈α
the␈αtag␈αpart.␈α
 The␈αlast␈αtwo␈α
were␈αthree␈αbits␈α
each␈αand␈αseparated␈α
from␈αeach␈αother␈α
by
␈↓ α∧␈↓the decrement so that they could not be easily combined into a single six bit part.

␈↓ α∧␈↓␈↓ αTAt␈αthis␈αpoint␈αthere␈αwas␈αsome␈α
indecision␈αabout␈αwhat␈αthe␈αbasic␈αoperators␈αshould␈α
be,␈αbecause
␈↓ α∧␈↓the␈α∞operation␈α∂of␈α∞extracting␈α∞a␈α∂part␈α∞of␈α∞the␈α∂word␈α∞by␈α∞masking␈α∂was␈α∞considered␈α∞separately␈α∂from␈α∞the
␈↓ α∧␈↓operation␈αof␈αtaking␈αthe␈αcontents␈αof␈αa␈αword␈αin␈α
memory␈αas␈αa␈αfunction␈αof␈αits␈αaddress.␈α At␈αthe␈αtime,␈α
it
␈↓ α∧␈↓seemed␈α⊂dubious␈α⊂to␈α⊂regard␈α⊂the␈α⊂latter␈α⊂operation␈α⊂as␈α⊂a␈α⊂function,␈α⊂since␈α⊂its␈α⊂value␈α⊂depended␈α⊂on␈α∂the
␈↓ α∧␈↓contents␈α⊃of␈α∩memory␈α⊃at␈α∩the␈α⊃time␈α∩the␈α⊃operation␈α⊃was␈α∩performed,␈α⊃so␈α∩it␈α⊃didn't␈α∩act␈α⊃like␈α∩a␈α⊃proper
␈↓ α∧␈↓mathematical␈α
function.␈α
 However,␈α
the␈α
advantages␈α
of␈αtreating␈α
it␈α
grammatically␈α
as␈α
a␈α
function␈αso␈α
that
␈↓ α∧␈↓it could be composed were also apparent.

␈↓ α∧␈↓␈↓ αTTherefore,␈α
the␈αinitially␈α
proposed␈α
set␈αof␈α
functions␈αincluded␈α
␈↓↓cwr␈↓,␈α
standing␈αfor␈α
"Contents␈αof␈α
the
␈↓ α∧␈↓Word␈α
in␈α∞Register␈α
number"␈α∞and␈α
four␈α∞functions␈α
that␈α∞extracted␈α
the␈α∞parts␈α
of␈α∞the␈α
word␈α∞and␈α
shifted
␈↓ α∧␈↓them␈αto␈αa␈αstandard␈αposition␈αat␈αthe␈αright␈αof␈αthe␈αword.␈α An␈αadditional␈αfunction␈αof␈αthree␈αarguments
␈↓ α∧␈↓that would also extract an arbitrary bit sequence was also proposed.

␈↓ α∧␈↓␈↓ αTIt␈αwas␈αsoon␈αnoticed␈αthat␈αextraction␈α
of␈αa␈αsubexpression␈αinvolved␈αcomposing␈αthe␈αextraction␈α
of
␈↓ α∧␈↓the␈αaddress␈αpart␈αwith␈α␈↓↓cwr␈↓␈αand␈αthat␈αcontinuing␈αalong␈αthe␈αlist␈αinvolved␈αcomposing␈αthe␈αextraction␈αof
␈↓ α∧␈↓the␈α∩decrement␈α∩part␈α∪with␈α∩␈↓↓cwr␈↓.␈α∩ Therefore,␈α∪the␈α∩compounds␈α∩␈↓↓car␈↓,␈α∪standing␈α∩for␈α∩"Contents␈α∪of␈α∩the
␈↓ α∧␈↓Address␈αpart␈αof␈αRegister␈αnumber",␈α
and␈αits␈αanalogs␈α␈↓↓cdr␈↓,␈α␈↓↓cpr␈↓,␈α
and␈α␈↓↓ctr␈↓␈αwere␈αdefined.␈α The␈α
motivation
␈↓ α∧␈↓for␈α∞implementing␈α
␈↓↓car␈↓␈α∞and␈α
␈↓↓cdr␈↓␈α∞separately␈α
was␈α∞strengthened␈α
by␈α∞the␈α
vulgar␈α∞fact␈α
that␈α∞the␈α∞IBM␈α
704
␈↓ α∧␈↓had␈α⊃instructions␈α⊃(connected␈α⊂with␈α⊃indexing)␈α⊃that␈α⊂made␈α⊃these␈α⊃operations␈α⊂easy␈α⊃to␈α⊃implement.␈α⊂ A
␈↓ α∧␈↓construct␈αoperation␈αfor␈αtaking␈αa␈αword␈αoff␈α
the␈αfree␈αstorage␈αlist␈αand␈αstuffing␈αit␈αwith␈α
given␈αcontents
␈↓ α∧␈↓was␈α
also␈α
obviously␈αrequired.␈α
 At␈α
some␈α
point␈αa␈α
␈↓↓cons(a,d,p,t)␈↓␈α
was␈α
defined,␈αbut␈α
it␈α
was␈α
regarded␈αas␈α
a
␈↓ α∧␈↓subroutine␈αand␈αnot␈αas␈αa␈αfunction␈αwith␈αa␈αvalue.␈α This␈αwork␈αwas␈αdone␈αat␈αDartmouth,␈αbut␈αnot␈αon␈αa
␈↓ α∧␈↓computer,␈α
since␈α
the␈α
New␈α
England␈α
Computation␈α
Center␈α
was␈α
not␈α
expected␈α
to␈α
receive␈α
its␈α∞IBM␈α
704
␈↓ α∧␈↓for another year.

␈↓ α∧␈↓␈↓ αTIn␈α⊗connection␈α⊗with␈α∃IBM's␈α⊗plane␈α⊗geometry␈α∃project,␈α⊗Nathaniel␈α⊗Rochester␈α⊗and␈α∃Herbert
␈↓ α∧␈↓Gelernter␈α∂(on␈α∂the␈α∞advice␈α∂of␈α∂McCarthy)␈α∞decided␈α∂to␈α∂implement␈α∞a␈α∂list␈α∂processing␈α∂language␈α∞within
␈↓ α∧␈↓FORTRAN,␈α
because␈α
this␈α
seemed␈αto␈α
the␈α
the␈α
easiest␈αway␈α
to␈α
get␈α
started,␈αand,␈α
in␈α
those␈α
days,␈αwriting␈α
a
␈↓ α∧␈↓compiler␈α
for␈α
a␈α
new␈α
language␈α
was␈α
believed␈α
to␈α
take␈α
many␈α
man-years.␈α
 This␈α
work␈α
was␈α
undertaken␈α
by
␈↓ α∧␈↓Herbert␈α
Gelernter␈α
and␈α
Carl␈α∞Gerberich␈α
at␈α
IBM␈α
and␈α
led␈α∞to␈α
FLPL,␈α
standing␈α
for␈α∞FORTRAN␈α
List
␈↓ α∧␈↓Processing␈αLanguage.␈α Gelernter␈αand␈αGerberich␈αnoticed␈αthat␈α␈↓↓cons␈↓␈αshould␈αbe␈αa␈αfunction,␈αnot␈αjust␈αa
␈↓ α∧␈↓subroutine,␈α
and␈α
that␈α
its␈α
value␈αshould␈α
be␈α
the␈α
location␈α
of␈α
the␈αword␈α
that␈α
had␈α
been␈α
taken␈α
from␈αthe
␈↓ α∧␈↓free␈α
storage␈α∞list.␈α
 This␈α∞permitted␈α
new␈α∞expressions␈α
to␈α∞be␈α
constructed␈α∞out␈α
of␈α∞subsubexpressions␈α
by
␈↓ α∧␈↓composing occurrences of ␈↓↓cons␈↓.

␈↓ α∧␈↓␈↓ αTWhile␈α∞expressions␈α∞could␈α∞be␈α∞handled␈α∞easily␈α∞in␈α∞FLPL,␈α∞and␈α∞it␈α∞was␈α∞used␈α∞successfully␈α∞for␈α∞the
␈↓ α∧␈↓Geometry␈αprogram,␈αit␈αhad␈αneither␈αconditional␈αexpressions␈αnor␈αrecursion,␈αand␈αerasing␈αlist␈αstructure
␈↓ α∧␈↓was handled explicitly by the program.
␈↓ α∧␈↓␈↓ u4


␈↓ α∧␈↓␈↓ αTI␈α
invented␈α∞conditional␈α
expressions␈α∞in␈α
connection␈α∞with␈α
a␈α
set␈α∞of␈α
chess␈α∞legal␈α
move␈α∞routines␈α
I
␈↓ α∧␈↓wrote␈αin␈αFORTRAN␈αfor␈αthe␈α
IBM␈α704␈αat␈αM.I.T.␈αduring␈α
1957-58.␈α This␈αprogram␈αdid␈αnot␈α
use␈αlist
␈↓ α∧␈↓processing.␈α
 The␈αIF␈α
statement␈α
provided␈αin␈α
FORTRAN␈α
1␈αand␈α
FORTRAN␈α
2␈αwas␈α
very␈αawkward␈α
to
␈↓ α∧␈↓use,␈αand␈αit␈αwas␈αnatural␈αto␈αinvent␈αa␈αfunction␈αXIF(M,N1,N2)␈αwhose␈αvalue␈αwas␈αN1␈αor␈αN2␈αaccording
␈↓ α∧␈↓to␈αwhether␈αthe␈αexpression␈αM␈αwas␈αzero␈αor␈αnot.␈α The␈αfunction␈αshortened␈αmany␈αprograms␈αand␈αmade
␈↓ α∧␈↓them␈αeasier␈αto␈αunderstand,␈αbut␈αit␈αhad␈αto␈αbe␈αused␈αsparingly,␈αbecause␈αall␈αthree␈αarguments␈αhad␈αto␈αbe
␈↓ α∧␈↓evaluated␈α⊂before␈α∂XIF␈α⊂was␈α⊂entered,␈α∂since␈α⊂XIF␈α∂was␈α⊂called␈α⊂as␈α∂an␈α⊂ordinary␈α⊂FORTRAN␈α∂function
␈↓ α∧␈↓though␈αwritten␈αin␈αmachine␈αlanguage.␈α This␈αled␈α
to␈αthe␈αinvention␈αof␈αthe␈αtrue␈αconditional␈α
expression
␈↓ α∧␈↓which␈αevaluates␈αonly␈αone␈α
of␈αN1␈αand␈αN2␈αaccording␈α
to␈αwhether␈αM␈αis␈αtrue␈α
or␈αfalse␈αand␈αto␈α
a␈αdesire
␈↓ α∧␈↓for a programming language that would allow its use.

␈↓ α∧␈↓␈↓ αTA␈αpaper␈αdefining␈αconditional␈αexpressions␈αand␈αproposing␈αtheir␈αuse␈αin␈αAlgol␈αwas␈αsent␈α
to␈αthe
␈↓ α∧␈↓␈↓↓Communications␈α
of␈α
the␈α
ACM␈↓␈αbut␈α
was␈α
arbitrarily␈α
demoted␈αto␈α
a␈α
letter␈α
to␈αthe␈α
editor,␈α
because␈α
it␈αwas
␈↓ α∧␈↓very short.

␈↓ α∧␈↓␈↓ αTI␈αspent␈αthe␈αsummer␈αof␈α1958␈αat␈αthe␈αIBM␈αInformation␈αResearch␈αDepartment␈αat␈αthe␈αinvitation
␈↓ α∧␈↓of␈α∞Nathaniel␈α∞Rochester␈α
and␈α∞chose␈α∞differentiating␈α
algebraic␈α∞expressions␈α∞as␈α
a␈α∞sample␈α∞problem.␈α
 It
␈↓ α∧␈↓led to the following innovations beyond FLPL:

␈↓ α∧␈↓␈↓ αTa.␈α∃Writing␈α∃recursive␈α∃function␈α∃definitions␈α∃using␈α∃conditional␈α∃expressions.␈α∃ The␈α∃idea␈α∀of
␈↓ α∧␈↓differentiation␈α⊂is␈α⊂obviously␈α∂recursive,␈α⊂and␈α⊂conditional␈α∂expressions␈α⊂allowed␈α⊂combining␈α⊂the␈α∂cases
␈↓ α∧␈↓into a single formula.

␈↓ α∧␈↓␈↓ αTb.␈α∞The␈α∞␈↓↓maplist␈↓␈α∞function␈α∞that␈α∞forms␈α∞a␈α
list␈α∞of␈α∞applications␈α∞of␈α∞a␈α∞functional␈α∞argument␈α∞to␈α
the
␈↓ α∧␈↓elements␈αof␈αa␈αlist.␈α This␈αwas␈αobviously␈αwanted␈αfor␈αdifferentiating␈αsums␈αof␈αarbitrarily␈αmany␈αterms,
␈↓ α∧␈↓and␈αwith␈α
a␈αslight␈α
modification,␈αit␈α
could␈αbe␈α
applied␈αto␈α
differentiating␈αproducts.␈α
 (The␈αoriginal␈α
form
␈↓ α∧␈↓was what is now called ␈↓↓mapcar␈↓).

␈↓ α∧␈↓␈↓ αTc.␈αTo␈αuse␈αfunctions␈αas␈αarguments,␈αone␈αneeds␈αa␈αnotation␈αfor␈αfunctions,␈αand␈αit␈αseemed␈αnatural
␈↓ α∧␈↓to␈α∂use␈α∂the␈α∂λ-notation␈α∂of␈α∂Church␈α∂(1941).␈α∂ I␈α∂didn't␈α∂understand␈α∂the␈α∂rest␈α∂of␈α∂his␈α∂book,␈α∂so␈α∂I␈α∂wasn't
␈↓ α∧␈↓tempted␈α∞to␈α∞try␈α∂to␈α∞implement␈α∞his␈α∂more␈α∞general␈α∞mechanism␈α∂for␈α∞defining␈α∞functions.␈α∂ Church␈α∞used
␈↓ α∧␈↓higher␈α⊂order␈α∂functionals␈α⊂instead␈α∂of␈α⊂using␈α∂conditional␈α⊂expressions.␈α∂ Conditional␈α⊂expressions␈α∂are
␈↓ α∧␈↓much more readily implemented on computers.

␈↓ α∧␈↓␈↓ αTd.␈αThe␈αrecursive␈αdefinition␈αof␈α
differentiation␈αmade␈αno␈αprovision␈αfor␈αerasure␈α
of␈αabandoned
␈↓ α∧␈↓list␈α⊂structure.␈α∂ No␈α⊂solution␈α∂was␈α⊂apparent␈α∂at␈α⊂the␈α∂time,␈α⊂but␈α∂the␈α⊂idea␈α∂of␈α⊂complicating␈α⊂the␈α∂elegant
␈↓ α∧␈↓definition␈α
of␈α
differentiation␈α
with␈α
explicit␈α
erasure␈α
was␈α
unattractive.␈α
 Needless␈α
to␈α
say,␈α
the␈α
point␈αof
␈↓ α∧␈↓the␈αexercise␈αwas␈αnot␈αthe␈αdifferentiation␈αprogram␈αitself,␈αseveral␈αof␈αwhich␈αhad␈αalready␈αbeen␈αwritten,
␈↓ α∧␈↓but rather clarification of the operations involved in symbolic computation.

␈↓ α∧␈↓␈↓ αTIn␈α∩fact,␈α∩the␈α∩differentiation␈α∩program␈α∩was␈α∩not␈α∩implemented␈α∩that␈α∩summer,␈α∩because␈α⊃FLPL
␈↓ α∧␈↓allows␈α⊃neither␈α⊃conditional␈α⊃expressions␈α⊂nor␈α⊃recursive␈α⊃use␈α⊃of␈α⊂subroutines.␈α⊃ At␈α⊃this␈α⊃point␈α⊃a␈α⊂new
␈↓ α∧␈↓language␈α
was␈α
necessary,␈α
since␈α
it␈α
was␈α∞very␈α
difficult␈α
both␈α
technically␈α
and␈α
politically␈α
to␈α∞tinker␈α
with
␈↓ α∧␈↓Fortran,␈α∞and␈α∞neither␈α∂conditional␈α∞expressions␈α∞nor␈α∞recursion␈α∂could␈α∞be␈α∞implemented␈α∂with␈α∞machine
␈↓ α∧␈↓language␈α⊂Fortran␈α⊂functions␈α⊂-␈α⊂not␈α⊂even␈α⊂with␈α⊂"functions"␈α⊂that␈α⊂modify␈α⊂the␈α⊂code␈α⊂that␈α⊂calls␈α⊂them.
␈↓ α∧␈↓Moreover,␈α
the␈α
IBM␈α
group␈α
seemed␈α
satisfied␈α
with␈α
FLPL␈α
as␈α
it␈α
was␈α
and␈α
did␈α
not␈α
want␈α
to␈α
make␈α
the
␈↓ α∧␈↓vaguely␈α∀stated␈α∪but␈α∀obviously␈α∀drastic␈α∪changes␈α∀required␈α∀to␈α∪allow␈α∀conditional␈α∀expressions␈α∪and
␈↓ α∧␈↓recursive definition.  As I recall, they argued that these were unnecessary.

␈↓ α∧␈↓2. The implementation of LISP.
␈↓ α∧␈↓␈↓ u5


␈↓ α∧␈↓␈↓ αTIn␈α∞the␈α∞Fall␈α∂of␈α∞1958,␈α∞I␈α∂became␈α∞Assistant␈α∞Professor␈α∞of␈α∂Communication␈α∞Sciences␈α∞(in␈α∂the␈α∞EE
␈↓ α∧␈↓Department)␈α∩at␈α∩M.I.T.,␈α⊃and␈α∩Marvin␈α∩Minsky␈α⊃(then␈α∩an␈α∩assistant␈α⊃professor␈α∩in␈α∩the␈α⊃Mathematics
␈↓ α∧␈↓Department)␈α
and␈α∞I␈α
started␈α
the␈α∞M.I.T.␈α
Artificial␈α
Intelligence␈α∞Project.␈α
 The␈α
Project␈α∞was␈α
supported
␈↓ α∧␈↓by␈α
the␈α
M.I.T.␈α
Research␈αLaboratory␈α
of␈α
Electronics␈α
which␈α
had␈αa␈α
contract␈α
from␈α
the␈α
armed␈αservices
␈↓ α∧␈↓that␈αpermitted␈αgreat␈αfreedom␈αto␈αthe␈αDirector,␈αProfessor␈αJerome␈αWiesner,␈αin␈αinitiating␈αnew␈αprojects
␈↓ α∧␈↓that␈α∂seemed␈α∞to␈α∂him␈α∂of␈α∞scientific␈α∂interest.␈α∂ No␈α∞written␈α∂proposal␈α∂was␈α∞ever␈α∂made.␈α∂ When␈α∞Wiesner
␈↓ α∧␈↓asked␈αMinsky␈αand␈αme␈αwhat␈αwe␈αneeded␈αfor␈αthe␈αproject,␈αwe␈αasked␈αfor␈αa␈αroom,␈αtwo␈αprogrammers,␈αa
␈↓ α∧␈↓secretary␈α
and␈αa␈α
keypunch,␈αand␈α
he␈αasked␈α
us␈αto␈α
also␈αundertake␈α
the␈αsupervision␈α
of␈αsome␈α
of␈α
the␈αsix
␈↓ α∧␈↓mathematics graduate students that R.L.E. had undertaken to support.

␈↓ α∧␈↓␈↓ αTThe␈α⊂implementation␈α⊂of␈α⊃LISP␈α⊂began␈α⊂in␈α⊃Fall␈α⊂1958.␈α⊂ The␈α⊂original␈α⊃idea␈α⊂was␈α⊂to␈α⊃produce␈α⊂a
␈↓ α∧␈↓compiler,␈α∂but␈α∞this␈α∂was␈α∞considered␈α∂a␈α∞major␈α∂undertaking,␈α∞and␈α∂we␈α∞needed␈α∂some␈α∂experimenting␈α∞in
␈↓ α∧␈↓order␈αto␈αget␈αgood␈αconventions␈αfor␈αsubroutine␈αlinking,␈αstack␈αhandling␈αand␈αerasure.␈α
 Therefore,␈αwe
␈↓ α∧␈↓started␈α∞by␈α∞hand-compiling␈α
various␈α∞functions␈α∞into␈α∞assembly␈α
language␈α∞and␈α∞writing␈α∞subroutines␈α
to
␈↓ α∧␈↓provide␈αa␈αLISP␈α"environment".␈α These␈αincluded␈αprograms␈αto␈αread␈αand␈αprint␈αlist␈αstructure.␈α I␈αcan't
␈↓ α∧␈↓now␈α∂remember␈α∂whether␈α∂the␈α∂decision␈α∂to␈α∂use␈α∂parenthesized␈α∂list␈α∂notation␈α∂as␈α∂the␈α∂external␈α∂form␈α∞of
␈↓ α∧␈↓LISP␈α∀data␈α∀was␈α∀made␈α∃then␈α∀or␈α∀whether␈α∀it␈α∀had␈α∃already␈α∀been␈α∀used␈α∀in␈α∀discussing␈α∃the␈α∀paper
␈↓ α∧␈↓differentiation program.

␈↓ α∧␈↓␈↓ αTThe␈α∀programs␈α∪to␈α∀be␈α∪hand-compiled␈α∀were␈α∀written␈α∪in␈α∀an␈α∪informal␈α∀notation␈α∀called␈α∪M-
␈↓ α∧␈↓expressions␈α⊃intended␈α⊃to␈α∩resemble␈α⊃FORTRAN␈α⊃as␈α∩much␈α⊃as␈α⊃possible.␈α∩ Besides␈α⊃FORTRAN-like
␈↓ α∧␈↓assignment␈α⊂statements␈α⊃and␈α⊂␈↓αgo to␈↓s,␈α⊂the␈α⊃language␈α⊂allowed␈α⊂conditional␈α⊃expressions␈α⊂and␈α⊃the␈α⊂basic
␈↓ α∧␈↓functions␈α∂of␈α∞LISP.␈α∂ Allowing␈α∞recursive␈α∂function␈α∞definitions␈α∂required␈α∞no␈α∂new␈α∞notation␈α∂from␈α∞the
␈↓ α∧␈↓function␈α
definitions␈α
allowed␈α∞in␈α
FORTRAN␈α
I␈α
-␈α∞only␈α
the␈α
removal␈α
of␈α∞the␈α
restriction␈α
-␈α
as␈α∞I␈α
recall,
␈↓ α∧␈↓unstated␈α⊂in␈α⊂the␈α⊂FORTRAN␈α⊂manual␈α⊂-␈α⊂forbidding␈α⊂recursive␈α⊂definitions.␈α⊂ The␈α⊃M-notation␈α⊂also
␈↓ α∧␈↓used␈α∂brackets␈α∂instead␈α∂of␈α∂parentheses␈α∂to␈α∂enclose␈α∂the␈α∂arguments␈α∂of␈α∂functions␈α∂in␈α∂order␈α⊂to␈α∂reserve
␈↓ α∧␈↓parentheses␈α
for␈α
list-structure␈α
constants.␈α
 It␈α
was␈α
intended␈α
to␈α
compile␈α
from␈α
some␈α∞approximation␈α
to
␈↓ α∧␈↓the␈αM-notation,␈αbut␈αthe␈αM-notation␈αwas␈αnever␈αfully␈αdefined,␈αbecause␈αrepresenting␈αLISP␈α
functions
␈↓ α∧␈↓by␈α⊂LISP␈α⊂lists␈α⊂became␈α⊂the␈α⊂dominant␈α∂programming␈α⊂language␈α⊂when␈α⊂the␈α⊂interpreter␈α⊂later␈α∂became
␈↓ α∧␈↓available.␈α A␈αmachine␈αreadable␈αM-notation␈αwould␈αhave␈αrequired␈αredefinition,␈αbecause␈αthe␈α
pencil-
␈↓ α∧␈↓and-paper M-notation used characters unavailable on the IBM 026 key punch.

␈↓ α∧␈↓␈↓ αTThe␈α∩READ␈α∪and␈α∩PRINT␈α∪programs␈α∩induced␈α∩a␈α∪␈↓↓de␈α∩facto␈↓␈α∪standard␈α∩external␈α∪notation␈α∩for
␈↓ α∧␈↓symbolic␈α%information,␈α$e.g.␈α%representing␈α$␈↓↓x + 3y + z␈↓␈α%by␈α%(PLUS X (TIMES 3 Y) Z)␈α$and
␈↓ α∧␈↓␈↓↓(∀x)(P(x)∨Q(x,y))␈↓␈α∪by␈α∪(ALL (X) (OR (P X) (Q X Y))).␈α∩ Any␈α∪other␈α∪notation␈α∪necessarily␈α∩requires
␈↓ α∧␈↓special␈α⊗programming,␈α⊗because␈α⊗standard␈α↔mathematical␈α⊗notations␈α⊗treat␈α⊗different␈α↔operators␈α⊗in
␈↓ α∧␈↓syntactically␈αdifferent␈αways.␈α This␈αnotation␈αlater␈αcame␈αto␈αbe␈αcalled␈α"Cambridge␈αPolish",␈αbecause␈αit
␈↓ α∧␈↓resembled␈αthe␈αprefix␈αnotation␈αof␈α
Lukasiewicz,␈αand␈αbecause␈αwe␈αnoticed␈α
that␈αQuine␈αhad␈αalso␈αused␈α
a
␈↓ α∧␈↓parenthesized prefix notation.

␈↓ α∧␈↓␈↓ αTThe␈α
erasure␈α
problem␈αalso␈α
had␈α
to␈α
be␈αconsidered,␈α
and␈α
it␈α
was␈αclearly␈α
unaesthetic␈α
to␈αuse␈α
explicit
␈↓ α∧␈↓erasure␈α∞as␈α∞did␈α∞IPL.␈α∞ There␈α∞were␈α∞two␈α∞alternatives.␈α∞ The␈α∞first␈α∞was␈α∞to␈α∞erase␈α∞the␈α∞old␈α∞contents␈α∂of␈α∞a
␈↓ α∧␈↓program␈α∞variable␈α∞whenever␈α
it␈α∞was␈α∞updated.␈α
 Since␈α∞the␈α∞␈↓↓car␈↓␈α
and␈α∞␈↓↓cdr␈↓␈α∞operations␈α
were␈α∞not␈α∞to␈α
copy
␈↓ α∧␈↓structure,␈α⊂merging␈α⊂list␈α∂structure␈α⊂would␈α⊂occur,␈α∂and␈α⊂erasure␈α⊂would␈α∂require␈α⊂a␈α⊂system␈α⊂of␈α∂reference
␈↓ α∧␈↓counts.␈α∞ Since␈α∞there␈α∞were␈α∞only␈α∞six␈α∞bits␈α∞left␈α∞in␈α∞a␈α∞word,␈α∞and␈α∞these␈α∞were␈α∞in␈α∞separated␈α∞parts␈α∞of␈α
the
␈↓ α∧␈↓word,␈α
reference␈αcounts␈α
seemed␈αinfeasible␈α
without␈αa␈α
drastic␈αchange␈α
in␈αthe␈α
way␈αlist␈α
structures␈αwere
␈↓ α∧␈↓represented.␈α (A␈αlist␈αhandling␈αscheme␈αusing␈αreference␈αcounts␈αwas␈αlater␈αused␈αby␈αCollins␈α(1960)␈αon␈αa
␈↓ α∧␈↓48 bit CDC computer).
␈↓ α∧␈↓␈↓ u6


␈↓ α∧␈↓␈↓ αTThe␈α∞second␈α∂alternative␈α∞is␈α∂␈↓↓garbage␈α∞collection␈↓␈α∂in␈α∞which␈α∂storage␈α∞is␈α∂abandoned␈α∞until␈α∂the␈α∞free
␈↓ α∧␈↓storage␈α
list␈α
is␈α
exhausted,␈α
the␈α
storage␈α
accessible␈α
from␈α
program␈α
variables␈α
and␈α
the␈α
stack␈α
is␈α
marked,
␈↓ α∧␈↓and␈α∂the␈α∂unmarked␈α∂storage␈α∂is␈α∂made␈α∂into␈α∂a␈α∂new␈α∂free␈α∂storage␈α∂list.␈α∂ Once␈α∂we␈α∂decided␈α∂on␈α∞garbage
␈↓ α∧␈↓collection,␈α∂its␈α∂actual␈α∂implementation␈α∂could␈α∂be␈α∞postponed,␈α∂because␈α∂only␈α∂toy␈α∂examples␈α∂were␈α∞being
␈↓ α∧␈↓done.

␈↓ α∧␈↓␈↓ αTAt␈α∂that␈α∞time␈α∂it␈α∞was␈α∂also␈α∞decided␈α∂to␈α∞use␈α∂SAVE␈α∞and␈α∂UNSAVE␈α∞routines␈α∂that␈α∞use␈α∂a␈α∞single
␈↓ α∧␈↓contiguous␈α
public␈αstack␈α
array␈αto␈α
save␈α
the␈αvalues␈α
of␈αvariables␈α
and␈αsubroutine␈α
return␈α
addresses␈αin
␈↓ α∧␈↓the␈α
implementation␈α
of␈α
recursive␈α
subroutines.␈α
 IPL␈α
built␈α
stacks␈α
as␈α
list␈α
structure␈α
and␈α
their␈α
use␈α
had␈α
to
␈↓ α∧␈↓be␈αexplicitly␈αprogrammed.␈α Another␈αdecision␈αwas␈αto␈αgive␈αup␈αthe␈αprefix␈αand␈αtag␈αparts␈αof␈αthe␈αword,
␈↓ α∧␈↓to␈α
abandon␈α
␈↓↓cwr␈↓,␈α
and␈αto␈α
make␈α
␈↓↓cons␈↓␈α
a␈α
function␈αof␈α
two␈α
arguments.␈α
 This␈αleft␈α
us␈α
with␈α
only␈α
a␈αsingle
␈↓ α∧␈↓type - the 15 bit address - so that the language didn't require declarations.

␈↓ α∧␈↓␈↓ αTThese␈α⊃simplifications␈α⊃made␈α∩LISP␈α⊃into␈α⊃a␈α⊃way␈α∩of␈α⊃describing␈α⊃computable␈α∩functions␈α⊃much
␈↓ α∧␈↓neater␈α
than␈α
the␈α
Turing␈α
machines␈α
or␈α
the␈α
general␈α
recursive␈α
definitions␈α
used␈α
in␈α∞recursive␈α
function
␈↓ α∧␈↓theory.␈α⊂ The␈α∂fact␈α⊂that␈α∂Turing␈α⊂machines␈α∂constitute␈α⊂an␈α∂awkward␈α⊂programming␈α⊂language␈α∂doesn't
␈↓ α∧␈↓much␈α⊂bother␈α∂recursive␈α⊂function␈α⊂theorists,␈α∂because␈α⊂they␈α∂almost␈α⊂never␈α⊂have␈α∂any␈α⊂reason␈α⊂to␈α∂write
␈↓ α∧␈↓particular␈α∂recursive␈α∂definitions,␈α∂since␈α∂the␈α∂theory␈α∂concerns␈α∂recursive␈α∂functions␈α∂in␈α⊂general.␈α∂ They
␈↓ α∧␈↓often␈αhave␈αreason␈αto␈αprove␈αthat␈αrecursive␈αfunctions␈αwith␈αspecific␈αproperties␈αexist,␈αbut␈αthis␈αcan␈αbe
␈↓ α∧␈↓done␈α
by␈αan␈α
informal␈α
argument␈αwithout␈α
having␈αto␈α
write␈α
them␈αdown␈α
explicitly.␈α
 In␈αthe␈α
early␈αdays␈α
of
␈↓ α∧␈↓computing,␈αsome␈αpeople␈α
developed␈αprogramming␈αlanguages␈αbased␈α
on␈αTuring␈αmachines;␈αperhaps␈α
it
␈↓ α∧␈↓seemed␈α∃more␈α⊗scientific.␈α∃ Anyway,␈α⊗I␈α∃decided␈α⊗to␈α∃write␈α∃a␈α⊗paper␈α∃describing␈α⊗LISP␈α∃both␈α⊗as␈α∃a
␈↓ α∧␈↓programming␈α
language␈α
and␈αas␈α
a␈α
formalism␈αfor␈α
doing␈α
recursive␈αfunction␈α
theory.␈α
 The␈α
paper␈αwas
␈↓ α∧␈↓␈↓↓Recursive␈α∞functions␈α
of␈α∞symbolic␈α
expressions␈α∞and␈α∞their␈α
computation␈α∞by␈α
machine,␈α∞part␈α∞I␈↓␈α
(McCarthy
␈↓ α∧␈↓1960).␈α⊂ Part␈α∂II␈α⊂was␈α∂never␈α⊂written␈α⊂but␈α∂was␈α⊂intended␈α∂to␈α⊂contain␈α∂applications␈α⊂to␈α⊂computing␈α∂with
␈↓ α∧␈↓algebraic␈α⊂expressions.␈α⊂ The␈α⊂paper␈α⊂had␈α⊂no␈α⊂influence␈α⊂on␈α⊂recursive␈α⊂function␈α⊂theorists,␈α⊂because␈α∂it
␈↓ α∧␈↓didn't address the questions that interested them.

␈↓ α∧␈↓␈↓ αTOne␈α_mathematical␈α_consideration␈α↔that␈α_influenced␈α_LISP␈α↔was␈α_to␈α_express␈α_programs␈α↔as
␈↓ α∧␈↓applicative␈α⊂expressions␈α∂built␈α⊂up␈α∂from␈α⊂variables␈α⊂and␈α∂constants␈α⊂using␈α∂functions.␈α⊂ I␈α⊂considered␈α∂it
␈↓ α∧␈↓important␈α∞to␈α∞make␈α∂these␈α∞expressions␈α∞obey␈α∞the␈α∂usual␈α∞mathematical␈α∞laws␈α∞allowing␈α∂replacement␈α∞of
␈↓ α∧␈↓expressions␈αby␈αexpressions␈α
giving␈αthe␈αsame␈α
value.␈α The␈αmotive␈αwas␈α
to␈αallow␈αproofs␈α
of␈αproperties
␈↓ α∧␈↓of␈αprograms␈αusing␈αordinary␈αmathematical␈αmethods.␈α This␈αis␈αonly␈αpossible␈αto␈αthe␈αextent␈αthat␈αside-
␈↓ α∧␈↓effects␈α_can␈α→be␈α_avoided.␈α_ Unfortunately,␈α→side-effects␈α_are␈α_often␈α→a␈α_great␈α→convenience␈α_when
␈↓ α∧␈↓computational␈α∩efficiency␈α∪is␈α∩important,␈α∩and␈α∪"functions"␈α∩with␈α∩side-effects␈α∪are␈α∩present␈α∪in␈α∩LISP.
␈↓ α∧␈↓However,␈α
the␈αso-called␈α
pure␈α
LISP␈αis␈α
free␈αof␈α
side-effects,␈α
and␈α(Cartwright␈α
1976)␈α
and␈α(Cartwright
␈↓ α∧␈↓and␈α
McCarthy␈α
1978)␈α
show␈α
how␈α
to␈α∞represent␈α
pure␈α
LISP␈α
programs␈α
by␈α
sentences␈α
and␈α∞schemata␈α
in
␈↓ α∧␈↓first␈αorder␈αlogic␈αand␈αprove␈αtheir␈αproperties.␈α This␈αis␈αan␈αadditional␈αvindication␈αof␈αthe␈αstriving␈αfor
␈↓ α∧␈↓mathematical␈α⊂neatness,␈α∂because␈α⊂it␈α∂is␈α⊂now␈α⊂easier␈α∂to␈α⊂prove␈α∂that␈α⊂pure␈α∂LISP␈α⊂programs␈α⊂meet␈α∂their
␈↓ α∧␈↓specifications␈α∂than␈α∂it␈α∂is␈α∞for␈α∂any␈α∂other␈α∂programming␈α∂language␈α∞in␈α∂extensive␈α∂use.␈α∂ (Fans␈α∂of␈α∞other
␈↓ α∧␈↓programming␈αlanguages␈αare␈αchallenged␈αto␈αwrite␈αa␈αprogram␈αto␈αconcatenate␈αlists␈αand␈αprove␈αthat␈αthe
␈↓ α∧␈↓operation is associative).

␈↓ α∧␈↓␈↓ αTAnother␈αway␈αto␈αshow␈αthat␈αLISP␈αwas␈αneater␈αthan␈αTuring␈αmachines␈αwas␈αto␈αwrite␈αa␈αuniversal
␈↓ α∧␈↓LISP␈α∂function␈α∂and␈α∂show␈α∂that␈α∞it␈α∂is␈α∂briefer␈α∂and␈α∂more␈α∞comprehensible␈α∂than␈α∂the␈α∂description␈α∂of␈α∞a
␈↓ α∧␈↓universal␈αTuring␈αmachine.␈α This␈αwas␈αthe␈αLISP␈αfunction␈α␈↓↓eval[e,a]␈↓,␈αwhich␈αcomputes␈αthe␈αvalue␈αof␈αa
␈↓ α∧␈↓LISP␈α
expression␈α
␈↓↓e␈↓␈α
-␈α
the␈α
second␈α
argument␈α
␈↓↓a␈↓␈α
being␈α
a␈α
list␈α
of␈α
assignments␈α
of␈α
values␈α
to␈α
variables.␈α
 (␈↓↓a␈↓␈α
is
␈↓ α∧␈↓needed␈α⊂to␈α∂make␈α⊂the␈α∂recursion␈α⊂work).␈α⊂ Writing␈α∂␈↓↓eval␈↓␈α⊂required␈α∂inventing␈α⊂a␈α⊂notation␈α∂representing
␈↓ α∧␈↓LISP␈α
functions␈αas␈α
LISP␈αdata,␈α
and␈αsuch␈α
a␈αnotation␈α
was␈αdevised␈α
for␈αthe␈α
purposes␈αof␈α
the␈αpaper␈α
with
␈↓ α∧␈↓␈↓ u7


␈↓ α∧␈↓no␈α∂thought␈α∂that␈α∂it␈α∞would␈α∂be␈α∂used␈α∂to␈α∂express␈α∞LISP␈α∂programs␈α∂in␈α∂practice.␈α∂ Logical␈α∞completeness
␈↓ α∧␈↓required␈αthat␈αthe␈αnotation␈αused␈αto␈αexpress␈αfunctions␈αused␈αas␈αfunctional␈αarguments␈αbe␈αextended␈αto
␈↓ α∧␈↓provide␈α
for␈α
recursive␈α
functions,␈α
and␈α∞the␈α
LABEL␈α
notation␈α
was␈α
invented␈α
by␈α∞Nathaniel␈α
Rochester
␈↓ α∧␈↓for␈αthat␈α
purpose.␈α D.M.R.␈α
Park␈αpointed␈αout␈α
that␈αLABEL␈α
was␈αlogically␈α
unnecessary␈αsince␈αthe␈α
result
␈↓ α∧␈↓could␈α
be␈α
achieved␈α
using␈α∞only␈α
LAMBDA␈α
-␈α
by␈α∞a␈α
construction␈α
analogous␈α
to␈α∞Church's␈α
␈↓↓Y␈↓-operator,
␈↓ α∧␈↓albeit in a more complicated way.

␈↓ α∧␈↓␈↓ αTS.R.␈αRussell␈αnoticed␈αthat␈α␈↓↓eval␈↓␈αcould␈αserve␈αas␈αan␈αinterpreter␈αfor␈αLISP,␈αpromptly␈αhand␈αcoded
␈↓ α∧␈↓it, and we now had a programming language with an interpreter.

␈↓ α∧␈↓␈↓ αTThe␈α∞unexpected␈α∂appearance␈α∞of␈α∞an␈α∂interpreter␈α∞tended␈α∂to␈α∞freeze␈α∞the␈α∂form␈α∞of␈α∂the␈α∞language,
␈↓ α∧␈↓and␈αsome␈αof␈αthe␈αdecisions␈αmade␈αrather␈αlightheartedly␈αfor␈αthe␈α"Recursive␈αfunctions␈α..."␈α
paper␈αlater
␈↓ α∧␈↓proved␈αunfortunate.␈α These␈αincluded␈αthe␈αCOND␈αnotation␈αfor␈αconditional␈αexpressions␈αwhich␈αleads
␈↓ α∧␈↓to␈αan␈αunnecessary␈αdepth␈αof␈αparentheses,␈αand␈αthe␈α
use␈αof␈αthe␈αnumber␈αzero␈αto␈αdenote␈αthe␈α
empty␈αlist
␈↓ α∧␈↓NIL␈αand␈αthe␈αtruth␈αvalue␈α␈↓αfalse␈↓.␈α Besides␈αencouraging␈αpornographic␈αprogramming,␈αgiving␈αa␈αspecial
␈↓ α∧␈↓interpretation to the address 0 has caused difficulties in all subsequent implementations.

␈↓ α∧␈↓␈↓ αTAnother␈αreason␈αfor␈αthe␈αinitial␈αacceptance␈αof␈αawkwardnesses␈αin␈αthe␈αinternal␈αform␈αof␈αLISP␈αis
␈↓ α∧␈↓that␈α∞we␈α
still␈α∞expected␈α
to␈α∞switch␈α∞to␈α
writing␈α∞programs␈α
as␈α∞M-expressions.␈α
 The␈α∞project␈α∞of␈α
defining
␈↓ α∧␈↓M-expressions␈α
precisely␈α∞and␈α
compiling␈α∞them␈α
or␈α
at␈α∞least␈α
translating␈α∞them␈α
into␈α∞S-expressions␈α
was
␈↓ α∧␈↓neither␈α
finalized␈α
nor␈α
explicitly␈αabandoned.␈α
 It␈α
just␈α
receded␈α
into␈αthe␈α
indefinite␈α
future,␈α
and␈α
a␈αnew
␈↓ α∧␈↓generation␈αof␈αprogrammers␈αappeared␈αwho␈α
preferred␈αinternal␈αnotation␈αto␈αany␈α
FORTRAN-like␈αor
␈↓ α∧␈↓ALGOL-like notation that could be devised.

␈↓ α∧␈↓3. From LISP I to LISP 1.5.

␈↓ α∧␈↓␈↓ αTa.␈αProperty␈αlists.␈α The␈αidea␈αof␈αproviding␈αeach␈αatom␈αwith␈αa␈αlist␈αof␈αproperties␈αwas␈αpresent␈αin
␈↓ α∧␈↓the␈αfirst␈αassembly␈αlanguage␈αimplementation.␈α
 It␈αwas␈αalso␈αone␈αof␈α
the␈αtheoretical␈αideas␈αof␈αthe␈α
Advice
␈↓ α∧␈↓Taker,␈αalthough␈αthe␈αAdvice␈αTaker␈α(McCarthy␈α1959)␈αwould␈αhave␈αrequired␈αa␈αproperty␈αlist␈αfor␈αany
␈↓ α∧␈↓expression␈α⊃about␈α⊃which␈α⊃information␈α⊃was␈α⊃known␈α⊃that␈α⊃did␈α⊃not␈α⊃follow␈α⊃from␈α⊃its␈α∩structure.␈α⊃ The
␈↓ α∧␈↓READ␈α
and␈α
PRINT␈α
programs␈α
required␈α
that␈α
the␈α
print␈α
names␈α
of␈α
atoms␈α
be␈α
accessible,␈α
and␈α
as␈α
soon␈α
as
␈↓ α∧␈↓function␈αdefinition␈αbecame␈αpossible,␈αit␈αwas␈αnecessary␈αto␈αindicate␈αwhether␈αa␈αfunction␈αwas␈αa␈αSUBR
␈↓ α∧␈↓in␈α∞machine␈α
code␈α∞or␈α
was␈α∞an␈α
EXPR␈α∞represented␈α
by␈α∞list␈α
structure.␈α∞ Several␈α
functions␈α∞dealing␈α
with
␈↓ α∧␈↓property lists were also made available for application programs which made heavy use of them.

␈↓ α∧␈↓␈↓ αTb.␈αInsertion␈α
of␈αelements␈αin␈α
lists␈αand␈α
their␈αdeletion.␈α One␈α
of␈αthe␈α
original␈αadvertised␈αvirtues␈α
of
␈↓ α∧␈↓list␈α∞processing␈α
for␈α∞AI␈α∞work␈α
was␈α∞the␈α
ability␈α∞to␈α∞insert␈α
and␈α∞delete␈α
elements␈α∞of␈α∞lists.␈α
 Unfortunately,
␈↓ α∧␈↓this␈α⊃facility␈α⊃coexists␈α⊃uneasily␈α⊂with␈α⊃shared␈α⊃list␈α⊃structure.␈α⊂ Moreover,␈α⊃operations␈α⊃that␈α⊃insert␈α⊂and
␈↓ α∧␈↓delete␈α
don't␈α
have␈α
a␈α
neat␈α
representation␈α
as␈α
functions.␈α
 LISP␈α
has␈α
them␈α
in␈α
the␈α
form␈α
of␈α
the␈α
␈↓↓rplaca␈↓␈α
and
␈↓ α∧␈↓␈↓↓rplacd␈↓␈αpseudo-functions,␈αbut␈αprograms␈αthat␈αuse␈αthem␈αcannot␈αbe␈αconveniently␈αrepresented␈αin␈αlogic,
␈↓ α∧␈↓because, regarded as functions, they don't permit replacement of equals by equals.

␈↓ α∧␈↓␈↓ αTc.␈α
Numbers.␈α
 Many␈α
computations␈α
require␈α
both␈α
numbers␈α
and␈α
symbolic␈αexpressions.␈α
 Numbers
␈↓ α∧␈↓were␈αoriginally␈αimplemented␈αin␈αLISP␈αI␈αas␈αlists␈αof␈αatoms,␈αand␈αthis␈αproved␈αtoo␈αslow␈αfor␈αall␈α
but␈αthe
␈↓ α∧␈↓simplest␈α∃computations.␈α∃ A␈α⊗reasonably␈α∃efficient␈α∃implementation␈α∃of␈α⊗numbers␈α∃as␈α∃atoms␈α⊗in␈α∃S-
␈↓ α∧␈↓expressions␈α
was␈α
made␈αin␈α
LISP␈α
1.5,␈α
but␈αin␈α
all␈α
the␈α
early␈αLISPs,␈α
numerical␈α
computations␈α
were␈αstill␈α
10
␈↓ α∧␈↓to␈α100␈αtimes␈αslower␈αthan␈αin␈αFORTRAN.␈α Efficient␈αnumerical␈αcomputation␈αrequires␈αsome␈αform␈αof
␈↓ α∧␈↓typing␈α∞in␈α∞the␈α∞source␈α∞language␈α∞and␈α∞a␈α∞distinction␈α∞between␈α∞numbers␈α∞treated␈α∞by␈α∞themselves␈α∞and␈α
as
␈↓ α∧␈↓elements␈α∞of␈α∞S-expressions.␈α∞ Some␈α∞recent␈α∞versions␈α∞of␈α∞LISP␈α∞allow␈α∞distinguishing␈α∞types,␈α∞but␈α∞at␈α∞the
␈↓ α∧␈↓time, this seemed incompatible with other features.
␈↓ α∧␈↓␈↓ u8


␈↓ α∧␈↓␈↓ αTd.␈α∪Free␈α∪variables.␈α∪ In␈α∩all␈α∪innocence,␈α∪James␈α∪R.␈α∩Slagle␈α∪programmed␈α∪the␈α∪following␈α∩LISP
␈↓ α∧␈↓function definition and complained when it didn't work right:

␈↓ α∧␈↓␈↓ αT␈↓↓testr[x,p,f,u]␈α.←␈α-␈↓αif␈↓↓␈α.p[x]␈α.␈↓αthen␈↓↓␈α-f[x]␈α.␈↓αelse␈↓↓␈α.␈↓αif␈↓↓␈α-atom[x]␈α.␈↓αthen␈↓↓␈α.u[]␈α-␈↓αelse␈↓↓
␈↓ α∧␈↓↓testr[cdr[x],p,f,λ:testr[car[x],p,f,u]]␈↓.

␈↓ α∧␈↓The␈αobject␈αof␈αthe␈αfunction␈αis␈αto␈αfind␈αa␈αsubexpression␈αof␈α␈↓↓x␈↓␈αsatisfying␈α␈↓↓p[x]␈↓␈αand␈αreturn␈α␈↓↓f[x].␈↓␈α
If␈αthe
␈↓ α∧␈↓search␈αis␈αunsuccessful,␈αthen␈αthe␈αcontinuation␈αfunction␈α␈↓↓u[]␈↓␈αof␈αno␈αarguments␈αis␈αto␈αbe␈αcomputed␈αand
␈↓ α∧␈↓its␈αvalue␈αreturned.␈α The␈αdifficulty␈αwas␈αthat␈αwhen␈αan␈αinner␈αrecursion␈αoccurred,␈αthe␈αvalue␈αof␈α␈↓↓car[x]␈↓
␈↓ α∧␈↓wanted␈α
was␈α
the␈αouter␈α
value,␈α
but␈α
the␈αinner␈α
value␈α
was␈α
actually␈αused.␈α
 In␈α
modern␈αterminology,␈α
lexical
␈↓ α∧␈↓scoping was wanted, and dynamic scoping was obtained.

␈↓ α∧␈↓␈↓ αTI␈α
must␈α∞confess␈α
that␈α
I␈α∞regarded␈α
this␈α
difficulty␈α∞as␈α
just␈α
a␈α∞bug␈α
and␈α
expressed␈α∞confidence␈α
that
␈↓ α∧␈↓Steve␈α
Russell␈α
would␈α
soon␈α
fix␈α∞it.␈α
 He␈α
did␈α
fix␈α
it␈α∞but␈α
by␈α
inventing␈α
the␈α
so-called␈α∞FUNARG␈α
device
␈↓ α∧␈↓that␈α∞took␈α∞the␈α∞lexical␈α∞environment␈α∞along␈α∞with␈α∞the␈α∞functional␈α∞argument.␈α∞ Similar␈α∞difficulties␈α
later
␈↓ α∧␈↓showed␈αup␈α
in␈αAlgol␈α60,␈α
and␈αRussell's␈αturned␈α
out␈αto␈αbe␈α
one␈αof␈αthe␈α
more␈αcomprehensive␈αsolutions␈α
to
␈↓ α∧␈↓the␈α∞problem.␈α
 While␈α∞it␈α∞worked␈α
well␈α∞in␈α∞the␈α
interpreter,␈α∞comprehensiveness␈α∞and␈α
speed␈α∞seem␈α∞to␈α
be
␈↓ α∧␈↓opposed␈α
in␈α
compiled␈α
code,␈α
and␈α
this␈α
led␈αto␈α
a␈α
succession␈α
of␈α
compromises.␈α
 Unfortunately,␈α
time␈αdid
␈↓ α∧␈↓not␈α∞permit␈α∞writing␈α∞an␈α∞appendix␈α
giving␈α∞the␈α∞history␈α∞of␈α∞the␈α
problem,␈α∞and␈α∞the␈α∞interested␈α∞reader␈α
is
␈↓ α∧␈↓referred␈αto␈α(Moses␈α1970)␈αas␈αa␈αplace␈αto␈αstart.␈α (David␈αPark␈αtells␈αme␈αthat␈αPatrick␈αFischer␈αalso␈αhad␈αa
␈↓ α∧␈↓hand in developing the FUNARG device).

␈↓ α∧␈↓␈↓ αTe.␈α∂The␈α∂"program␈α∂feature".␈α⊂ Besides␈α∂composition␈α∂of␈α∂functions␈α∂and␈α⊂conditional␈α∂expressions,
␈↓ α∧␈↓LISP␈αalso␈α
allows␈αsequential␈α
programs␈αwritten␈α
with␈αassignment␈α
statements␈αand␈α
␈↓αgo to␈↓s.␈α Compared
␈↓ α∧␈↓to␈α∞the␈α
mathematically␈α∞elegant␈α∞recursive␈α
function␈α∞definition␈α∞features,␈α
the␈α∞"program␈α∞feature"␈α
looks
␈↓ α∧␈↓like␈α∞a␈α∞hasty␈α∞afterthought.␈α∞ This␈α∞is␈α∞not␈α∞quite␈α∞correct;␈α∞the␈α∞idea␈α∞of␈α∞having␈α∞sequential␈α∞programs␈α∞in
␈↓ α∧␈↓LISP␈α
antedates␈α
that␈αof␈α
having␈α
recursive␈αfunction␈α
definition.␈α
 However,␈αthe␈α
notation␈α
LISP␈αuses␈α
for
␈↓ α∧␈↓PROGs was definitely an afterthought and is far from optimal.

␈↓ α∧␈↓␈↓ αTf.␈αOnce␈α
the␈α␈↓↓eval␈↓␈α
interpreter␈αwas␈α
programmed,␈αit␈α
became␈αavailable␈α
to␈αthe␈α
programmer,␈αand␈α
it
␈↓ α∧␈↓was␈α∩especially␈α∩easy␈α∩to␈α∩use␈α∩because␈α∩it␈α⊃interprets␈α∩LISP␈α∩programs␈α∩expressed␈α∩as␈α∩LISP␈α∩data.␈α⊃ In
␈↓ α∧␈↓particular,␈α∞␈↓↓eval␈↓␈α
made␈α∞possible␈α
FEXPRS␈α∞and␈α
FSUBRS␈α∞which␈α
are␈α∞"functions"␈α
that␈α∞are␈α∞not␈α
given
␈↓ α∧␈↓their␈αactual␈αarguments␈αbut␈αare␈α
given␈αthe␈αexpressions␈αthat␈αevaluate␈α
to␈αthe␈αarguments␈αand␈αmust␈α
call
␈↓ α∧␈↓␈↓↓eval␈↓␈α
themselves␈α
when␈α
they␈α
want␈α
the␈α
expressions␈α
evaluated.␈α
 The␈α
main␈α
application␈α
of␈α
this␈α
facility␈α
is
␈↓ α∧␈↓to␈α∞functions␈α
that␈α∞don't␈α
always␈α∞evaluate␈α
all␈α∞of␈α
their␈α∞arguments;␈α
they␈α∞evaluate␈α
some␈α∞of␈α∞them␈α
first,
␈↓ α∧␈↓and␈α∂then␈α∂decide␈α⊂which␈α∂others␈α∂to␈α⊂evaluate.␈α∂ This␈α∂facility␈α⊂resembles␈α∂Algol's␈α∂␈↓↓call-by-name␈↓␈α⊂but␈α∂is
␈↓ α∧␈↓more␈α∞flexible,␈α∞because␈α∞␈↓↓eval␈↓␈α∞is␈α∞explicitly␈α
available.␈α∞ A␈α∞first␈α∞order␈α∞logic␈α∞treatment␈α∞of␈α
"extensional"
␈↓ α∧␈↓FEXPRs and FSUBRs now seems possible.

␈↓ α∧␈↓␈↓ αTg.␈αSince␈αLISP␈α
works␈αwith␈αlists,␈αit␈α
was␈αalso␈αconvenient␈αto␈α
provide␈αfor␈αfunctions␈αwith␈α
variable
␈↓ α∧␈↓numbers␈α⊃of␈α⊃arguments␈α⊃by␈α⊃supplying␈α⊃them␈α⊃with␈α⊃a␈α⊃list␈α⊃of␈α⊃arguments␈α⊃rather␈α⊃than␈α∩the␈α⊃separate
␈↓ α∧␈↓arguments.

␈↓ α∧␈↓␈↓ αTUnfortunately,␈α∩none␈α∩of␈α∩the␈α∩above␈α∩features␈α∩has␈α∩been␈α∩given␈α∩a␈α∩comprehensive␈α∪and␈α∩clear
␈↓ α∧␈↓mathematical␈α
semantics␈αin␈α
connection␈αwith␈α
LISP␈α
or␈αany␈α
other␈αprogramming␈α
language.␈α
 The␈αbest
␈↓ α∧␈↓attempt in connection with LISP is Michael Gordon's (1973), but it is too complicated.

␈↓ α∧␈↓␈↓ αTh.␈αThe␈αfirst␈αattempt␈αat␈αa␈αcompiler␈α
was␈αmade␈αby␈αRobert␈αBrayton,␈αbut␈αwas␈αunsuccessful.␈α
 The
␈↓ α∧␈↓first␈α∂successful␈α⊂LISP␈α∂compiler␈α∂was␈α⊂programmed␈α∂by␈α⊂Timothy␈α∂Hart␈α∂and␈α⊂Michael␈α∂Levin.␈α⊂ It␈α∂was
␈↓ α∧␈↓written in LISP and was claimed to be the first compiler written in the language to be compiled.
␈↓ α∧␈↓␈↓ u9


␈↓ α∧␈↓␈↓ αTMany␈α∞people␈α
participated␈α∞in␈α∞the␈α
initial␈α∞development␈α∞of␈α
LISP,␈α∞and␈α∞I␈α
haven't␈α∞been␈α∞able␈α
to
␈↓ α∧␈↓remember␈α⊃all␈α⊃their␈α∩contributions␈α⊃and␈α⊃must␈α⊃settle,␈α∩at␈α⊃this␈α⊃writing,␈α⊃for␈α∩a␈α⊃list␈α⊃of␈α⊃names.␈α∩ I␈α⊃can
␈↓ α∧␈↓remember␈α∞Paul␈α∞Abrahams,␈α∞Robert␈α∞Brayton,␈α∞Daniel␈α∞Edwards,␈α∞Patrick␈α∞Fischer,␈α∞Phyllis␈α∂Fox,␈α∞Saul
␈↓ α∧␈↓Goldberg,␈α∞Timothy␈α∞Hart,␈α∞Louis␈α∞Hodes,␈α∂Michael␈α∞Levin,␈α∞David␈α∞Luckham,␈α∞Klim␈α∂Maling,␈α∞Marvin
␈↓ α∧␈↓Minsky, David Park, Nathaniel Rochester of IBM, and Steve Russell.

␈↓ α∧␈↓␈↓ αTBesides␈αwork␈α
on␈αthe␈α
LISP␈αsystem,␈αmany␈α
applications␈αwere␈α
programmed,␈αand␈αthis␈α
experience
␈↓ α∧␈↓affected␈α
the␈α
system␈α
itself.␈α
 The␈α
main␈α
applications␈αthat␈α
I␈α
can␈α
remember␈α
are␈α
a␈α
program␈αby␈α
Rochester
␈↓ α∧␈↓and␈α∀Goldberg␈α∀on␈α∪symbolic␈α∀computation␈α∀of␈α∀impedances␈α∪and␈α∀other␈α∀functions␈α∀associated␈α∪with
␈↓ α∧␈↓electrical␈αnetworks,␈αJ.R.␈αSlagle's␈αthesis␈αwork␈αon␈αsymbolic␈αintegration␈αdirected␈αby␈αMinsky,␈αand␈αPaul
␈↓ α∧␈↓Abrahams' thesis on proof-checking.

␈↓ α∧␈↓4. Beyond LISP 1.5.

␈↓ α∧␈↓␈↓ αTAs␈αa␈αprogramming␈αlanguage␈αLISP␈αhad␈αmany␈αlimitations.␈α Some␈αof␈αthe␈αmost␈αevident␈αin␈αthe
␈↓ α∧␈↓early␈α⊂1960s␈α⊂were␈α⊂ultra-slow␈α⊂numerical␈α⊃computation,␈α⊂inability␈α⊂to␈α⊂represent␈α⊂objects␈α⊂by␈α⊃blocks␈α⊂of
␈↓ α∧␈↓registers␈α
and␈α
garbage␈α
collect␈α
the␈α
blocks,␈α
and␈α
lack␈α
of␈α
a␈α
good␈α
system␈α
for␈α
input-output␈α∞of␈α
symbolic
␈↓ α∧␈↓expressions␈αin␈αconventional␈αnotations.␈α All␈αthese␈αproblems␈αand␈αothers␈αwere␈αto␈αbe␈αfixed␈αin␈αLISP␈α2.
␈↓ α∧␈↓In␈αthe␈αmeantime,␈αwe␈αhad␈αto␈αsettle␈αfor␈αLISP␈α1.5␈αdeveloped␈αat␈αM.I.T.␈αwhich␈αcorrected␈αonly␈αthe␈αmost
␈↓ α∧␈↓glaring deficiencies.

␈↓ α∧␈↓␈↓ αTThe␈α⊗LISP␈α⊗2␈α⊗project␈α⊗was␈α↔a␈α⊗collaboration␈α⊗of␈α⊗Systems␈α⊗Development␈α↔Corporation␈α⊗and
␈↓ α∧␈↓Information␈α
International␈α
Inc.,␈αand␈α
was␈α
initially␈αplanned␈α
for␈α
the␈αQ32␈α
computer,␈α
which␈α
was␈αbuilt
␈↓ α∧␈↓by␈α
IBM␈α
for␈αmilitary␈α
purposes␈α
and␈αwhich␈α
had␈α
a␈α48␈α
bit␈α
word␈αand␈α
18␈α
bit␈αaddresses,␈α
i.e.,␈α
it␈αwas␈α
better
␈↓ α∧␈↓than␈α
the␈α
IBM␈α
7090␈α
for␈α
an␈α
ambitious␈α
project.␈α
 Unfortunately,␈α
the␈α
Q32␈α
at␈α
SDC␈α
was␈αnever␈α
equipped
␈↓ α∧␈↓with␈α∞more␈α∞than␈α∞48K␈α∞words␈α∞of␈α∞this␈α∞memory.␈α
 When␈α∞it␈α∞became␈α∞clear␈α∞that␈α∞the␈α∞Q32␈α∞had␈α∞too␈α
little
␈↓ α∧␈↓memory,␈αit␈α
was␈αdecided␈αto␈α
develop␈αthe␈αlanguage␈α
for␈αthe␈αIBM␈α
360/67␈αand␈αthe␈α
Digital␈αEquipment
␈↓ α∧␈↓PDP-6␈α-␈αSDC␈αwas␈αacquiring␈αthe␈αformer,␈αwhile␈αIII␈αand␈αM.I.T.␈α and␈αStanford␈αpreferred␈αthe␈αlatter.
␈↓ α∧␈↓The␈α
project␈α
proved␈α
more␈α
expensive␈α
than␈α
expected,␈α
the␈α
collaboration␈α
proved␈α
more␈α
difficult␈αthan
␈↓ α∧␈↓expected,␈αand␈αso␈αLISP␈α2␈αwas␈αdropped.␈α From␈αa␈α1970s␈αpoint␈αof␈αview,␈αthis␈αwas␈αregrettable,␈αbecause
␈↓ α∧␈↓much␈α
more␈α
money␈α
has␈α
since␈α
been␈α
spent␈α
to␈α
develop␈α
LISPs␈α
with␈α
fewer␈α
features.␈α
 However,␈α
it␈α
was
␈↓ α∧␈↓not␈αthen␈αknown␈αthat␈αthe␈αdominant␈αmachine␈αfor␈αAI␈αresearch␈αwould␈αbe␈αthe␈αPDP-10,␈αa␈αsuccessor␈αof
␈↓ α∧␈↓the␈α⊃PDP-6.␈α⊃ A␈α⊃part␈α⊃of␈α⊃the␈α⊃AI␈α⊃community,␈α∩e.g.␈α⊃BBN␈α⊃and␈α⊃SRI␈α⊃made␈α⊃what␈α⊃proved␈α⊃to␈α∩be␈α⊃an
␈↓ α∧␈↓architectural digression in doing AI work on the SDS 940 computer.

␈↓ α∧␈↓␈↓ αTThe␈α
existence␈α
of␈αan␈α
interpreter␈α
and␈αthe␈α
absence␈α
of␈αdeclarations␈α
makes␈α
it␈αparticularly␈α
natural
␈↓ α∧␈↓to␈α
use␈α
LISP␈α
in␈α
a␈α
time-sharing␈α
environment.␈α It␈α
is␈α
convenient␈α
to␈α
define␈α
functions,␈α
test␈α
them,␈αand
␈↓ α∧␈↓re-edit␈αthem␈αwithout␈αever␈αleaving␈αthe␈αLISP␈αinterpreter.␈α A␈αdemonstration␈αof␈αLISP␈αin␈αa␈αprototype
␈↓ α∧␈↓time-sharing␈α∞environment␈α∞on␈α∞the␈α∞IBM␈α∞704␈α∞was␈α∞made␈α∞in␈α∞1960␈α∞(or␈α∞1961).␈α∞(See␈α∞Appendix␈α∞2).␈α∞ L.
␈↓ α∧␈↓Peter␈α∞Deutsch␈α∞implemented␈α∞the␈α
first␈α∞interactive␈α∞LISP␈α∞on␈α∞the␈α
PDP-1␈α∞computer␈α∞in␈α∞1963,␈α∞but␈α
the
␈↓ α∧␈↓PDP-1 had too small a memory for serious symbolic computation.

␈↓ α∧␈↓␈↓ αTThe␈αmost␈αimportant␈αimplementations␈αof␈αLISP␈αproved␈αto␈αbe␈αthose␈αfor␈αthe␈αPDP-6␈αcomputer
␈↓ α∧␈↓and␈α⊗its␈α⊗successor␈α⊗the␈α∃PDP-10␈α⊗made␈α⊗by␈α⊗the␈α∃Digital␈α⊗Equipment␈α⊗Corporation␈α⊗of␈α∃Maynard,
␈↓ α∧␈↓Massachusetts.␈α∞ In␈α∂fact,␈α∞the␈α∂half␈α∞word␈α∂instructions␈α∞and␈α∂the␈α∞stack␈α∂instructions␈α∞of␈α∂these␈α∞machines
␈↓ α∧␈↓were␈αdeveloped␈αwith␈αLISP's␈αrequirements␈αin␈αmind.␈α The␈αearly␈αdevelopment␈αof␈αLISP␈αat␈αM.I.T.␈αfor
␈↓ α∧␈↓this␈α⊃line␈α⊃of␈α⊃machines␈α⊂and␈α⊃its␈α⊃subsequent␈α⊃development␈α⊂of␈α⊃INTERLISP␈α⊃(nee␈α⊃BBN␈α⊃LISP)␈α⊂and
␈↓ α∧␈↓MACLISP␈α∪also␈α∪contributed␈α∪to␈α∪making␈α∪these␈α∪machines␈α∪the␈α∪machines␈α∪of␈α∪choice␈α∪for␈α∩artificial
␈↓ α∧␈↓intelligence␈αresearch.␈α The␈αIBM␈α704␈αLISP␈αwas␈αextended␈αto␈αthe␈αIBM␈α7090␈αand␈αlater␈αled␈αto␈αLISPs
␈↓ α∧␈↓for the IBM 360 and 370.
␈↓ α∧␈↓␈↓ f10


␈↓ α∧␈↓␈↓ αTThe␈α∂earliest␈α∂publications␈α∂on␈α∂LISP␈α∂were␈α∂in␈α∂the␈α∂Quarterly␈α∂Progress␈α∂Reports␈α∂of␈α∂the␈α∂M.I.T.
␈↓ α∧␈↓Research␈α⊃Laboratory␈α⊂of␈α⊃Electronics.␈α⊂ (McCarthy␈α⊃1960)␈α⊂was␈α⊃the␈α⊂first␈α⊃journal␈α⊃publication.␈α⊂ The
␈↓ α∧␈↓␈↓↓LISP␈α∪Programmer's␈α∩Manual␈↓␈α∪by␈α∩Phyllis␈α∪Fox␈α∪was␈α∩published␈α∪by␈α∩the␈α∪Research␈α∪Laboratory␈α∩of
␈↓ α∧␈↓Electronics␈αin␈α1960␈αand␈αthe␈α␈↓↓LISP␈α1.5␈αProgrammer's␈αManual␈↓␈αby␈αMcCarthy,␈αLevin,␈αet.␈αal.␈α in␈α
1962
␈↓ α∧␈↓was␈αpublished␈αby␈αM.I.T.␈αPress.␈α After␈αthe␈αpublication␈αof␈α(McCarthy␈αand␈αLevin␈α1962),␈αmany␈α
LISP
␈↓ α∧␈↓implementations␈α
were␈α
made␈αfor␈α
numerous␈α
computers.␈α However,␈α
in␈α
contrast␈αto␈α
the␈α
situation␈αwith
␈↓ α∧␈↓most␈αwidely␈αused␈αprogramming␈αlanguages,␈αno␈α
organization␈αhas␈αever␈αattempted␈αto␈αpropagate␈α
LISP,
␈↓ α∧␈↓and␈α∂there␈α∞has␈α∂never␈α∂been␈α∞an␈α∂attempt␈α∂at␈α∞agreeing␈α∂on␈α∂a␈α∞standardization,␈α∂although␈α∂recently␈α∞A.C.
␈↓ α∧␈↓Hearn␈α∂has␈α∂developed␈α∂a␈α∂"standard␈α∞LISP"␈α∂(Marti,␈α∂Hearn,␈α∂Griss␈α∂and␈α∞Griss␈α∂1978)␈α∂that␈α∂runs␈α∂on␈α∞a
␈↓ α∧␈↓number␈α∞of␈α∞computers␈α∞in␈α∞order␈α∞to␈α∂support␈α∞the␈α∞REDUCE␈α∞system␈α∞for␈α∞computation␈α∂with␈α∞algebraic
␈↓ α∧␈↓expressions.

␈↓ α∧␈↓5. Conclusions.

␈↓ α∧␈↓␈↓ αTLISP␈α⊃is␈α⊂now␈α⊃the␈α⊂second␈α⊃oldest␈α⊂programming␈α⊃language␈α⊂in␈α⊃present␈α⊂widespread␈α⊃use␈α⊂(after
␈↓ α∧␈↓FORTRAN␈α∩and␈α⊃not␈α∩counting␈α⊃APT,␈α∩which␈α∩isn't␈α⊃used␈α∩for␈α⊃programming␈α∩␈↓↓per␈α⊃se␈↓).␈α∩ It␈α∩owes␈α⊃its
␈↓ α∧␈↓longevity␈α∪to␈α∩two␈α∪facts.␈α∩First,␈α∪its␈α∩core␈α∪occupies␈α∪some␈α∩kind␈α∪of␈α∩local␈α∪optimum␈α∩in␈α∪the␈α∪space␈α∩of
␈↓ α∧␈↓programming␈α~languages␈α~given␈α~that␈α~static␈α~friction␈α~discourages␈α~purely␈α~notational␈α~changes.
␈↓ α∧␈↓Recursive␈αuse␈α
of␈αconditional␈α
expressions,␈αrepresentation␈α
of␈αsymbolic␈α
information␈αexternally␈αby␈α
lists
␈↓ α∧␈↓and␈α
internally␈α
by␈α
list␈αstructure,␈α
and␈α
representation␈α
of␈α
program␈αin␈α
the␈α
same␈α
way␈α
will␈αprobably␈α
have
␈↓ α∧␈↓a very long life.

␈↓ α∧␈↓␈↓ αTSecond,␈α∂LISP␈α∂still␈α∂has␈α∂operational␈α∂features␈α∞unmatched␈α∂by␈α∂other␈α∂language␈α∂that␈α∂make␈α∂it␈α∞a
␈↓ α∧␈↓convenient␈α
vehicle␈αfor␈α
higher␈α
level␈αsystems␈α
for␈α
symbolic␈αcomputation␈α
and␈α
for␈αartificial␈α
intelligence.
␈↓ α∧␈↓These␈α
include␈α
its␈α
run-time␈α
system␈α
that␈α
give␈α
good␈αaccess␈α
to␈α
the␈α
features␈α
of␈α
the␈α
host␈α
machine␈αand␈α
its
␈↓ α∧␈↓operating␈α
system,␈α
its␈α
list␈αstructure␈α
internal␈α
language␈α
that␈α
makes␈αit␈α
a␈α
good␈α
target␈α
for␈αcompiling␈α
from
␈↓ α∧␈↓yet␈α∞higher␈α∞level␈α∞languages,␈α∂its␈α∞compatibility␈α∞with␈α∞systems␈α∂that␈α∞produce␈α∞binary␈α∞or␈α∂assembly␈α∞level
␈↓ α∧␈↓program,␈α∀and␈α∀the␈α∀availability␈α∀of␈α∀its␈α∪interpreter␈α∀as␈α∀a␈α∀command␈α∀language␈α∀for␈α∀driving␈α∪other
␈↓ α∧␈↓programs.␈α
 (One␈α
can␈α∞even␈α
conjecture␈α
that␈α
LISP␈α∞owes␈α
its␈α
survival␈α
specifically␈α∞to␈α
the␈α
fact␈α∞that␈α
its
␈↓ α∧␈↓programs␈α⊃are␈α⊂lists,␈α⊃which␈α⊂everyone,␈α⊃including␈α⊂me,␈α⊃has␈α⊂regarded␈α⊃as␈α⊂a␈α⊃disadvantage.␈α⊂ Proposed
␈↓ α∧␈↓replacements␈α∞for␈α∞LISP,␈α∞e.g.␈α∞POP-2␈α∞(Burstall␈α∞1968,1971),␈α∞abandoned␈α∞this␈α∞feature␈α∞in␈α∞favor␈α∂of␈α∞an
␈↓ α∧␈↓Algol-like syntax leaving no target language for higher level systems).

␈↓ α∧␈↓␈↓ αTLISP␈α∩will␈α∩become␈α∩obsolete␈α∩when␈α∩someone␈α∩makes␈α∩a␈α∩more␈α∩comprehensive␈α∪language␈α∩that
␈↓ α∧␈↓dominates␈α≠LISP␈α~practically␈α≠and␈α~also␈α≠gives␈α~a␈α≠clear␈α~mathematical␈α≠semantics␈α~to␈α≠a␈α~more
␈↓ α∧␈↓comprehensive set of features.

␈↓ α∧␈↓6. References.

␈↓ α∧␈↓␈↓αAbrahams,␈α∂Paul␈α∂W.␈α∞␈↓(1963),␈α∂␈↓↓Machine␈α∂verification␈α∞of␈α∂mathematical␈α∂proof,␈α∞␈↓␈α∂M.I.T.␈α∂PhD␈α∂thesis␈α∞in
␈↓ α∧␈↓mathematics.

␈↓ α∧␈↓␈↓αAbrahams,␈αPaul␈α
W.,␈αBarnett,␈αJ.,␈α
et␈αal.,␈α␈↓(1966),␈α
"The␈αLISP␈α2␈α
Programming␈αLanguage␈αand␈α
System",
␈↓ α∧␈↓␈↓↓Proceedings of the Fall Joint Computer Conference, ␈↓pp.  661-676.

␈↓ α∧␈↓␈↓αAbrahams,␈αPaul␈αW.␈α
␈↓(1967),␈α␈↓↓LISP␈α2␈α
Specifications,␈α␈↓Systems␈αDevelopment␈α
Corporation␈αTechnical
␈↓ α∧␈↓report TM-3417/200/00, Santa Monica, Calif.

␈↓ α∧␈↓␈↓αAllen, John ␈↓(1978), ␈↓↓Anatomy of LISP, ␈↓McGraw Hill.
␈↓ α∧␈↓␈↓ f11


␈↓ α∧␈↓␈↓αBerkeley,␈α∞Edmund␈α∂C.␈α∞and␈α∂Daniel␈α∞Bobrow,␈α∞eds.␈↓␈α∂(1964),␈α∞␈↓↓The␈α∂Programming␈α∞Language␈α∂LISP,␈α∞its
␈↓ α∧␈↓↓Operation␈α⊂and␈α⊂Applications␈↓,␈α⊂Information␈α⊂International␈α⊂Incorporated,␈α⊂Cambridge,␈α∂Massachusetts.
␈↓ α∧␈↓(out of print).

␈↓ α∧␈↓␈↓αBurstall,␈α∃R.M.,␈α∃J.S.␈α∃Collins␈α∃and␈α∃R.J.␈α∃Popplestone␈α∃␈↓(1968),␈α∃␈↓↓The␈α∃POP-2␈α∃Papers␈↓,␈α∀Edinburgh
␈↓ α∧␈↓University Press, Edinburgh, Scotland.

␈↓ α∧␈↓␈↓αBurstall,␈α∂R.M.,␈α⊂J.S.␈α∂Collins␈α∂and␈α⊂R.J.␈α∂Popplestone␈α∂␈↓(1971),␈α⊂␈↓↓Programming␈α∂in␈α⊂POP-2␈↓.␈α∂Edinburgh
␈↓ α∧␈↓University Press, Edinburgh, Scotland.

␈↓ α∧␈↓␈↓αCartwright,␈αRobert␈α␈↓(1976),␈α␈↓↓A␈αpractical␈αformal␈αsemantic␈αdefinition␈αand␈αverification␈αsystem␈αfor␈αtyped
␈↓ α∧␈↓↓LISP␈↓, Stanford Artificial Intelligence Laboratory technical report AIM-296, Stanford, California.

␈↓ α∧␈↓␈↓αCartwright,␈α
Robert␈α
and␈α∞John␈α
McCarthy␈↓␈α
(1978)␈α
"Representation␈α∞of␈α
Recursive␈α
Programs␈α∞in␈α
First
␈↓ α∧␈↓Order␈α∀Logic"␈α∀(to␈α∀be␈α∀published).␈α∀(Draft␈α∀available␈α∀as␈α∀FIRST.NEW[W77,JMC]␈α∀at␈α∀SU-AI␈α∀on
␈↓ α∧␈↓ARPAnet).

␈↓ α∧␈↓␈↓αCollins,␈αG.E.␈↓␈α
(1960)␈α"A␈αmethod␈α
for␈αoverlapping␈αand␈α
erasure␈αof␈αlists",␈α
␈↓↓Communications␈αof␈αthe␈α
ACM␈↓,
␈↓ α∧␈↓Vol. 3, pp. 655-657.

␈↓ α∧␈↓␈↓αChurch,␈αAlonzo␈α␈↓(1941),␈α␈↓↓Calculi␈αof␈αLambda␈αconversion,␈α␈↓Princeton␈αUniversity␈αPress,␈αPrinceton,␈αNew
␈↓ α∧␈↓Jersey.

␈↓ α∧␈↓␈↓αFox, Phyllis (1960) ␈↓↓LISP I Programmers Manual, ␈↓Internal paper, MIT, Cambridge, Mass.

␈↓ α∧␈↓␈↓αGordon,␈α∩Michael␈α∩␈↓(1973)␈α∩␈↓↓Models␈α∩of␈α∩Pure␈α∩LISP␈↓,␈α∩Experimental␈α∩Programming␈α∩Reports:␈α∪No.␈α∩31,
␈↓ α∧␈↓University of Edinburgh, Edinburgh.

␈↓ α∧␈↓␈↓αGelernter,␈α⊗H.,␈α∃J.␈α⊗R.␈α∃Hansen,␈α⊗and␈α∃C.␈α⊗L.␈α∃Gerberich␈α⊗␈↓(1960),␈α∃"A␈α⊗FORTRAN-Compiled␈α∃List
␈↓ α∧␈↓Processing Language", ␈↓↓Journal of the ACM␈↓, Vol. 7, No. 2, pp. 87-101.

␈↓ α∧␈↓␈↓αHearn,␈α∨Anthony␈α∨␈↓(1967),␈α∨␈↓↓REDUCE,␈α∨a␈α∨User-oriented␈α∨Interactive␈α∨System␈α for␈α∨Algebraic
␈↓ α∧␈↓↓Simplification,␈α⊃␈↓Stanford␈α∩Artificial␈α⊃Intelligence␈α⊃Laboratory␈α∩technical␈α⊃report␈α∩AIM-57,␈α⊃Stanford,
␈↓ α∧␈↓California.

␈↓ α∧␈↓␈↓αHewitt,␈α∪Carl␈α∪␈↓(1971),␈α∀␈↓↓Description␈α∪and␈α∪theoretical␈α∪analysis␈α∀(using␈α∪schemata)␈α∪of␈α∀PLANNER:␈α∪a
␈↓ α∧␈↓↓language␈α⊗for␈α⊗proving␈α↔theorems␈α⊗and␈α⊗manipulating␈α⊗models␈α↔in␈α⊗a␈α⊗robot,␈α⊗␈↓Ph.D.␈α↔Thesis,␈α⊗MIT,
␈↓ α∧␈↓Cambridge, Mass.

␈↓ α∧␈↓␈↓αMcCarthy,␈α⊂John␈α⊂␈↓(1958)␈α⊂"Programs␈α⊂with␈α⊃common␈α⊂sense",␈α⊂␈↓↓Proceedings␈α⊂of␈α⊂the␈α⊂Symposium␈α⊃on␈α⊂the
␈↓ α∧␈↓↓Mechanization of Thought Processes, ␈↓National Physiology Lab, Teddington, England.

␈↓ α∧␈↓␈↓αMcCarthy,␈α∂J.,␈α∂Minsky,␈α∂M.,␈α∂et␈α∂al.,␈α∂␈↓(1959a),␈α∂Quarterly␈α∂Progress␈α∂Report␈α∂No.␈α∂52,␈α∂Research␈α∂Lab␈α∞of
␈↓ α∧␈↓Electronics, MIT, Cambridge, Mass.

␈↓ α∧␈↓␈↓αMcCarthy,␈α∂J.,␈α∂Minsky,␈α∂M.,␈α∞et␈α∂al.,␈α∂␈↓(1959b),␈α∂Quarterly␈α∂Progress␈α∞Report␈α∂No.␈α∂55,␈α∂Research␈α∂Lab␈α∞of
␈↓ α∧␈↓Electronics, MIT, Cambridge, Mass.

␈↓ α∧␈↓␈↓αMcCarthy, John ␈↓(1959c), Letter to the Editor, ␈↓↓CACM, ␈↓Vol. 2, No. 8.
␈↓ α∧␈↓␈↓ f12


␈↓ α∧␈↓␈↓αMcCarthy,␈α∂J.,␈α∂Minsky,␈α∂M.,␈α∂et␈α∂al.,␈α∂␈↓(1960a),␈α∂Quarterly␈α∂Progress␈α∂Report␈α∂No.␈α∂56,␈α∂Research␈α∂Lab␈α∞of
␈↓ α∧␈↓Electronics, MIT, Cambridge, Mass.

␈↓ α∧␈↓␈↓αMcCarthy,␈α∞John␈α∞␈↓(1960b),␈α∞"Recursive␈α∞Functions␈α∞of␈α∞Symbolic␈α∞Expressions␈α∞and␈α∞their␈α
Computation
␈↓ α∧␈↓by Machine, part I",␈↓↓ CACM, ␈↓Vol. 3, No. 4, pp. 184-195.

␈↓ α∧␈↓␈↓αMcCarthy,␈αJ.,␈αMinsky,␈αM.,␈α
et␈αal.,␈α␈↓(1962a),␈αQuarterly␈α
Progress␈αReport,␈αResearch␈αLab␈αof␈α
Electronics,
␈↓ α∧␈↓MIT, Cambridge, Mass.

␈↓ α∧␈↓␈↓αMcCarthy,␈α∂J.,␈α∂Minsky,␈α∂M.,␈α∞et␈α∂al.,␈α∂␈↓(1962b),␈α∂Quarterly␈α∂Progress␈α∞Report␈α∂No.␈α∂64,␈α∂Research␈α∂Lab␈α∞of
␈↓ α∧␈↓Electronics, MIT, Cambridge, Mass.

␈↓ α∧␈↓␈↓αMcCarthy,␈αJohn␈α␈↓(1962c),␈α␈↓↓LISP␈α1.5␈αProgrammer's␈αManual,␈α␈↓(with␈αAbrahams,␈αEdwards,␈αHart,␈α
and
␈↓ α∧␈↓Levin), MIT Press, Cambridge, Mass.

␈↓ α∧␈↓␈↓αMcCarthy,␈α∂J.,␈α∂Minsky,␈α∂M.,␈α∂et␈α∂al.,␈α∂␈↓(1963a),␈α∂Quarterly␈α∂Progress␈α∂Report␈α∂No.␈α∂68,␈α∂Research␈α∂Lab␈α∞of
␈↓ α∧␈↓Electronics, MIT, Cambridge, Mass.

␈↓ α∧␈↓␈↓αMcCarthy,␈α∂J.,␈α∂Minsky,␈α∂M.,␈α∞et␈α∂al.,␈α∂␈↓(1963b),␈α∂Quarterly␈α∂Progress␈α∞Report␈α∂No.␈α∂69,␈α∂Research␈α∂Lab␈α∞of
␈↓ α∧␈↓Electronics, MIT, Cambridge, Mass.

␈↓ α∧␈↓␈↓αMcCarthy,␈α∞John␈↓␈α∂(1963c)␈α∞"A␈α∂Basis␈α∞for␈α∂a␈α∞Mathematical␈α∂Theory␈α∞of␈α∂Computation",␈α∞in␈α∂P.␈α∞Braffort
␈↓ α∧␈↓and␈αD.␈αHirschberg␈α
(eds.),␈α␈↓↓Computer␈αProgramming␈αand␈α
Formal␈αSystems␈↓,␈αpp.␈α33-70.␈α
 North-Holland
␈↓ α∧␈↓Publishing Company, Amsterdam.

␈↓ α∧␈↓␈↓αMcCarthy,␈αJohn␈α
␈↓(1963d)␈α"Towards␈αa␈α
Mathematical␈αScience␈αof␈α
Computation",␈α␈↓↓Proceedings␈αof␈α
IFIP
␈↓ α∧␈↓↓Congress, Munich 1962␈↓, Amsterdam: North-Holland, pp. 21-28.

␈↓ α∧␈↓␈↓αMcCarthy,␈α⊂J.,␈α⊂Minsky,␈α⊂M.,␈α⊂et␈α⊂al.,␈α⊂␈↓(1965),␈α⊂Quarterly␈α⊂Progress␈α⊂Report␈α⊂No.␈α⊂76,␈α⊂Research␈α⊂Lab␈α⊂of
␈↓ α∧␈↓Electronics, MIT, Cambridge, Mass.

␈↓ α∧␈↓␈↓αMcCarthy,␈α⊂J.,␈α⊂Minsky,␈α⊂M.,␈α⊂et␈α⊂al.,␈α⊂␈↓(1966),␈α⊂Quarterly␈α⊂Progress␈α⊂Report␈α⊂No.␈α⊂80,␈α⊂Research␈α⊂Lab␈α⊂of
␈↓ α∧␈↓Electronics, MIT, Cambridge, Mass.

␈↓ α∧␈↓␈↓αMcCarthy,␈α∂John␈α∂and␈α∂Carolyn␈α∂Talcott␈↓␈α∂(1979)␈α∂␈↓↓LISP␈α∂with␈α∂Proofs␈↓,␈α∂to␈α∂be␈α∂published.␈α∂ Versions␈α∞of
␈↓ α∧␈↓most chapters are available at the Stanford Artificial Intelligence Laboratory.

␈↓ α∧␈↓␈↓αMarti,␈αJ.␈αB.,␈αHearn,␈αA.␈αC.,␈αGriss,␈αM.␈αL.and␈αGriss,␈αC.␈α␈↓(1978)␈α␈↓↓Standard␈αLISP␈αReport,␈α␈↓University␈αof
␈↓ α∧␈↓Utah Symbolic Computation Group Report No 60, Provo, Utah.

␈↓ α∧␈↓␈↓αThe␈α∞Mathlab␈α∞Group␈α∞␈↓(1977),␈α∞␈↓↓MACSYMA␈α∞Reference␈α∞Manual,␈α∞␈↓Laboratory␈α∞for␈α∞Computer␈α∞Science,
␈↓ α∧␈↓MIT Version 9, Cambridge, Mass.

␈↓ α∧␈↓␈↓αMitchell,␈αR.W.␈α␈↓(1964)␈α␈↓↓LISP␈α2␈α
Specifications␈αProposal,␈α␈↓Stanford␈αArtificial␈αIntelligence␈α
Laboratory
␈↓ α∧␈↓Memo No. 21, Stanford, Calif.

␈↓ α∧␈↓␈↓αMoon,␈α∂David␈α∂A.␈α∂␈↓(1974),␈α∂␈↓↓MACLISP␈α∂Reference␈α∂Manual,␈α∂␈↓Project␈α∂MAC␈α∂Technical␈α⊂Report,␈α∂MIT,
␈↓ α∧␈↓Cambridge, Mass.
␈↓ α∧␈↓␈↓ f13


␈↓ α∧␈↓␈↓αMoses,␈αJoel␈α␈↓(1970)␈α␈↓↓The␈αfunction␈αof␈αFUNCTION␈αin␈αLISP␈αor␈αwhy␈αthe␈αFUNARG␈αproblem␈αshould␈αbe
␈↓ α∧␈↓↓called the environment problem␈↓", M.I.T. Artificial Intelligence Memo 199, Cambridge, Mass.

␈↓ α∧␈↓␈↓αNewell,␈α
A.,␈α
and␈αJ.C.␈α
Shaw␈α
␈↓(1957)␈α"Programming␈α
the␈α
Logic␈αTheory␈α
Machine",␈α
␈↓↓Proceedings␈α
of␈αthe
␈↓ α∧␈↓↓1957 Western Joint Computer Conference, ␈↓IRE.

␈↓ α∧␈↓␈↓αRulifson,␈α∃J.␈α∃et␈α∃al.␈α∃␈↓(1968),␈α⊗"QA4␈α∃-␈α∃A␈α∃Language␈α∃for␈α∃Writing␈α⊗Problem-Solving␈α∃Programs",
␈↓ α∧␈↓␈↓↓Proceeding IFIP 1968 Congress, ␈↓TA-2, pp 111-115.

␈↓ α∧␈↓␈↓αStoyan,␈αHerbert␈↓.␈α Herbert␈αStoyan␈αof␈αDresden,␈α
DDR␈αhas␈αcompleted␈αseveral␈αchapters␈αon␈αthe␈α
history
␈↓ α∧␈↓of LISP.

␈↓ α∧␈↓␈↓αSussman,␈αG.␈αWinograd,␈αT.,␈αand␈αCharniak,␈α
E.␈α␈↓(1970),␈α␈↓↓Microplanner␈αReference␈αManual,␈α␈↓AI␈α
Memo
␈↓ α∧␈↓203, AIL MIT, Camridge, Mass.

␈↓ α∧␈↓␈↓αTeitelman,␈α∂Warren␈α∂␈↓(1975),␈α∂␈↓↓INTERLISP:␈α⊂Interlisp␈α∂Reference␈α∂Manual,␈α∂Xerox␈α⊂PARC␈α∂Technical
␈↓ α∧␈↓↓Report, Palo Alto, Calif.

␈↓ α∧␈↓↓␈↓αWeisman, Clark ␈↓(1967), ␈↓↓LISP 1.5 Primer, ␈↓Dickenson Press.

␈↓ α∧␈↓Many␈α⊂reports␈α⊃and␈α⊂memoranda␈α⊂of␈α⊃the␈α⊂M.I.T.␈α⊂and␈α⊃Stanford␈α⊂Artificial␈α⊃Intelligence␈α⊂Laboratories
␈↓ α∧␈↓have dealt with various aspects of LISP and higher level systems built on LISP.

␈↓ α∧␈↓APPENDIX - HUMOROUS ANECDOTE

␈↓ α∧␈↓␈↓ αTThe␈α
first␈α
on-line␈α
demonstration␈α
of␈α
LISP␈α
was␈α
also␈α
the␈α
first␈α
of␈α
a␈α
precursor␈α
of␈α
time-sharing
␈↓ α∧␈↓that␈α∀we␈α∪called␈α∀"time-stealing".␈α∪ The␈α∀audience␈α∪comprised␈α∀the␈α∪participants␈α∀in␈α∪one␈α∀of␈α∪M.I.T.'s
␈↓ α∧␈↓Industrial␈α
Liaison␈α
Symposia␈α
on␈α
whom␈α
it␈α
was␈α
important␈α
to␈α
make␈α
a␈α
good␈α
impression.␈α
 A␈α
Flexowriter
␈↓ α∧␈↓had␈α∩been␈α⊃connected␈α∩to␈α∩the␈α⊃IBM␈α∩704␈α⊃and␈α∩the␈α∩operating␈α⊃system␈α∩modified␈α⊃so␈α∩that␈α∩it␈α⊃collected
␈↓ α∧␈↓characters␈α∞from␈α∞the␈α∞Flexowriter␈α∞in␈α∞a␈α∂buffer␈α∞when␈α∞their␈α∞presence␈α∞was␈α∞signalled␈α∞by␈α∂an␈α∞interrupt.
␈↓ α∧␈↓Whenever␈α↔a␈α↔carriage␈α⊗return␈α↔occurred,␈α↔the␈α⊗line␈α↔was␈α↔given␈α⊗to␈α↔LISP␈α↔for␈α↔processing.␈α⊗ The
␈↓ α∧␈↓demonstration␈α∞depended␈α∞on␈α∞the␈α∂fact␈α∞that␈α∞the␈α∞memory␈α∞of␈α∂the␈α∞computer␈α∞had␈α∞just␈α∂been␈α∞increased
␈↓ α∧␈↓from␈α∞8192␈α∞words␈α
to␈α∞32768␈α∞words␈α
so␈α∞that␈α∞batches␈α
could␈α∞be␈α∞collected␈α
that␈α∞presumed␈α∞only␈α∞a␈α
small
␈↓ α∧␈↓memory.

␈↓ α∧␈↓␈↓ αTThe␈αdemonstration␈αwas␈αalso␈α
one␈αof␈αthe␈αfirst␈α
to␈αuse␈αclosed␈αcircuit␈α
TV␈αin␈αorder␈αto␈α
spare␈αthe
␈↓ α∧␈↓spectators␈α
the␈α
museum␈α
feet␈α
consequent␈α
on␈α
crowding␈α
around␈α
a␈α
terminal␈α
waiting␈α
for␈α∞something␈α
to
␈↓ α∧␈↓happen.␈α∩ Thus␈α∩they␈α∪were␈α∩on␈α∩the␈α∪fourth␈α∩floor,␈α∩and␈α∪I␈α∩was␈α∩in␈α∪the␈α∩first␈α∩floor␈α∪computer␈α∩room
␈↓ α∧␈↓exercising␈αLISP␈αand␈αspeaking␈αinto␈αa␈α
microphone.␈α The␈αproblem␈αchosen␈αwas␈αto␈αdetermine␈α
whether
␈↓ α∧␈↓a␈α∃first␈α∃order␈α∃differential␈α∃equation␈α∃of␈α⊗the␈α∃form␈α∃␈↓↓Mdx + Ndy␈↓␈α∃was␈α∃exact␈α∃by␈α⊗testing␈α∃whether
␈↓ α∧␈↓␈↓↓∂M/∂y = ∂N/∂x␈↓, which also involved some primitive algebraic simplification.

␈↓ α∧␈↓␈↓ αTEverything␈α
was␈α
going␈α
well,␈α
if␈α
slowly,␈α
when␈α
suddenly␈α
the␈α
Flexowriter␈α
began␈α
to␈α
type␈α∞(at␈α
ten
␈↓ α∧␈↓characters per second)

␈↓ α∧␈↓"THE␈α!GARBAGE␈α!COLLECTOR␈α!HAS␈α!BEEN␈α!CALLED.␈α" SOME␈α!INTERESTING
␈↓ α∧␈↓STATISTICS ARE AS FOLLOWS:"

␈↓ α∧␈↓and␈α
on␈αand␈α
on␈α
and␈αon.␈α
 The␈α
garbage␈αcollector␈α
was␈αquite␈α
new␈α
at␈αthe␈α
time,␈α
we␈αwere␈α
rather␈αproud␈α
of
␈↓ α∧␈↓␈↓ f14


␈↓ α∧␈↓it␈α∞and␈α∞curious␈α∞about␈α
it,␈α∞and␈α∞our␈α∞normal␈α∞output␈α
was␈α∞on␈α∞a␈α∞line␈α∞printer,␈α
so␈α∞it␈α∞printed␈α∞a␈α∞full␈α
page
␈↓ α∧␈↓every␈αtime␈αit␈αwas␈αcalled␈αgiving␈αhow␈αmany␈αwords␈αwere␈αmarked␈αand␈αhow␈αmany␈αwere␈αcollected␈αand
␈↓ α∧␈↓the␈α
size␈α
of␈α
list␈α∞space,␈α
etc.␈α
 During␈α
a␈α
previous␈α∞rehearsal,␈α
the␈α
garbage␈α
collector␈α
hadn't␈α∞been␈α
called,
␈↓ α∧␈↓but␈α∩we␈α∪had␈α∩not␈α∪refreshed␈α∩the␈α∩LISP␈α∪core␈α∩image,␈α∪so␈α∩we␈α∩ran␈α∪out␈α∩of␈α∪free␈α∩storage␈α∪during␈α∩the
␈↓ α∧␈↓demonstration.

␈↓ α∧␈↓␈↓ αTNothing␈α∩had␈α∩ever␈α∩been␈α∩said␈α∩about␈α∩a␈α∩garbage␈α∩collector,␈α∩and␈α∩I␈α∩could␈α∩only␈α∩imagine␈α⊃the
␈↓ α∧␈↓reaction␈α∂of␈α∂the␈α∂audience.␈α∂ We␈α∂were␈α∂already␈α⊂behind␈α∂time␈α∂on␈α∂a␈α∂tight␈α∂schedule,␈α∂it␈α∂was␈α⊂clear␈α∂that
␈↓ α∧␈↓typing␈α∩out␈α⊃the␈α∩garbage␈α⊃collector␈α∩message␈α∩would␈α⊃take␈α∩all␈α⊃the␈α∩remaining␈α⊃time␈α∩allocated␈α∩to␈α⊃the
␈↓ α∧␈↓demonstration,␈α∞and␈α∞both␈α∞the␈α∞lecturer␈α∞and␈α∞the␈α∞audience␈α∞were␈α∞incapacitated␈α∞by␈α∞laughter.␈α∂ I␈α∞think
␈↓ α∧␈↓some of them thought we were victims of a practical joker.

␈↓ α∧␈↓John McCarthy
␈↓ α∧␈↓Artificial Intelligence Laboratory
␈↓ α∧␈↓Computer Science Department
␈↓ α∧␈↓Stanford University
␈↓ α∧␈↓Stanford, California 94305

␈↓ α∧␈↓ARPANET: MCCARTHY@SU-AI

␈↓ α∧␈↓␈↓εThis draft of LISP[F77,JMC] PUBbed at 15:23 on April 18, 1979.␈↓